Coding Patterns
Heap & Priority Queue
Code Templates

Code Templates

This page provides standardized, memorizable code “blueprints” that can be adapted to most heap and priority queue problems. Each template includes implementations in multiple programming languages to help you master this essential pattern.

Before diving into these templates, make sure you understand the Concept Guide which explains when and why to use heap and priority queue patterns. These templates provide the practical implementation details you’ll need for coding interviews.

The “Main” Template: Binary Heap Implementation

This template provides the most common variation - a binary heap with array-based storage. It’s the foundation for most heap-based solutions.

Description: Array-based binary heap implementation that maintains the heap property through bubble up and sink down operations. This template directly solves problems like Kth Largest Element and Last Stone Weight.

class MaxHeap {
    constructor() {
        this.heap = [];
    }

    insert(val) {
        this.heap.push(val);
        this._bubbleUp(this.heap.length - 1);
    }

    extractMax() {
        if (this.heap.length === 1) return this.heap.pop();
        if (this.heap.length === 0) return null;

        const max = this.heap[0];
        this.heap[0] = this.heap.pop();
        this._sinkDown(0);
        return max;
    }

    peek() {
        return this.heap.length > 0 ? this.heap[0] : null;
    }

    size() {
        return this.heap.length;
    }

    _bubbleUp(idx) {
        const parentIdx = Math.floor((idx - 1) / 2);
        if (parentIdx >= 0 && this.heap[idx] > this.heap[parentIdx]) {
            [this.heap[idx], this.heap[parentIdx]] = [this.heap[parentIdx], this.heap[idx]];
            this._bubbleUp(parentIdx);
        }
    }

    _sinkDown(idx) {
        const leftIdx = 2 * idx + 1;
        const rightIdx = 2 * idx + 2;
        let largestIdx = idx;

        if (leftIdx < this.heap.length && this.heap[leftIdx] > this.heap[largestIdx]) {
            largestIdx = leftIdx;
        }
        if (rightIdx < this.heap.length && this.heap[rightIdx] > this.heap[largestIdx]) {
            largestIdx = rightIdx;
        }

        if (largestIdx !== idx) {
            [this.heap[idx], this.heap[largestIdx]] = [this.heap[largestIdx], this.heap[idx]];
            this._sinkDown(largestIdx);
        }
    }
}
class MaxHeap:
    def __init__(self):
        self.heap = []

    def insert(self, val):
        self.heap.append(val)
        self._bubble_up(len(self.heap) - 1)

    def extract_max(self):
        if len(self.heap) == 1:
            return self.heap.pop()
        if len(self.heap) == 0:
            return None

        max_val = self.heap[0]
        self.heap[0] = self.heap.pop()
        self._sink_down(0)
        return max_val

    def peek(self):
        return self.heap[0] if self.heap else None

    def size(self):
        return len(self.heap)

    def _bubble_up(self, idx):
        parent_idx = (idx - 1) // 2
        if parent_idx >= 0 and self.heap[idx] > self.heap[parent_idx]:
            self.heap[idx], self.heap[parent_idx] = self.heap[parent_idx], self.heap[idx]
            self._bubble_up(parent_idx)

    def _sink_down(self, idx):
        left_idx = 2 * idx + 1
        right_idx = 2 * idx + 2
        largest_idx = idx

        if left_idx < len(self.heap) and self.heap[left_idx] > self.heap[largest_idx]:
            largest_idx = left_idx
        if right_idx < len(self.heap) and self.heap[right_idx] > self.heap[largest_idx]:
            largest_idx = right_idx

        if largest_idx != idx:
            self.heap[idx], self.heap[largest_idx] = self.heap[largest_idx], self.heap[idx]
            self._sink_down(largest_idx)
public class MaxHeap {
    private int[] heap;
    private int size;

    public MaxHeap() {
        this.heap = new int[10];
        this.size = 0;
    }

    public void insert(int val) {
        if (size == heap.length) {
            resize();
        }
        heap[size] = val;
        bubbleUp(size);
        size++;
    }

    public int extractMax() {
        if (size == 0) return Integer.MIN_VALUE;

        int max = heap[0];
        heap[0] = heap[size - 1];
        size--;
        sinkDown(0);
        return max;
    }

    public int peek() {
        return size > 0 ? heap[0] : Integer.MIN_VALUE;
    }

    public int size() {
        return size;
    }

    private void bubbleUp(int idx) {
        int parentIdx = (idx - 1) / 2;
        if (parentIdx >= 0 && heap[idx] > heap[parentIdx]) {
            swap(idx, parentIdx);
            bubbleUp(parentIdx);
        }
    }

    private void sinkDown(int idx) {
        int leftIdx = 2 * idx + 1;
        int rightIdx = 2 * idx + 2;
        int largestIdx = idx;

        if (leftIdx < size && heap[leftIdx] > heap[largestIdx]) {
            largestIdx = leftIdx;
        }
        if (rightIdx < size && heap[rightIdx] > heap[largestIdx]) {
            largestIdx = rightIdx;
        }

        if (largestIdx != idx) {
            swap(idx, largestIdx);
            sinkDown(largestIdx);
        }
    }

    private void swap(int i, int j) {
        int temp = heap[i];
        heap[i] = heap[j];
        heap[j] = temp;
    }

    private void resize() {
        int[] newHeap = new int[heap.length * 2];
        System.arraycopy(heap, 0, newHeap, 0, heap.length);
        heap = newHeap;
    }
}
#include <vector>
#include <algorithm>

class MaxHeap {
private:
    std::vector<int> heap;

public:
    void insert(int val) {
        heap.push_back(val);
        bubbleUp(heap.size() - 1);
    }

    int extractMax() {
        if (heap.size() == 1) {
            int val = heap.back();
            heap.pop_back();
            return val;
        }
        if (heap.empty()) {
            return INT_MIN;
        }

        int maxVal = heap[0];
        heap[0] = heap.back();
        heap.pop_back();
        sinkDown(0);
        return maxVal;
    }

    int peek() {
        return heap.empty() ? INT_MIN : heap[0];
    }

    int size() {
        return heap.size();
    }

private:
    void bubbleUp(int idx) {
        int parentIdx = (idx - 1) / 2;
        if (parentIdx >= 0 && heap[idx] > heap[parentIdx]) {
            std::swap(heap[idx], heap[parentIdx]);
            bubbleUp(parentIdx);
        }
    }

    void sinkDown(int idx) {
        int leftIdx = 2 * idx + 1;
        int rightIdx = 2 * idx + 2;
        int largestIdx = idx;

        if (leftIdx < heap.size() && heap[leftIdx] > heap[largestIdx]) {
            largestIdx = leftIdx;
        }
        if (rightIdx < heap.size() && heap[rightIdx] > heap[largestIdx]) {
            largestIdx = rightIdx;
        }

        if (largestIdx != idx) {
            std::swap(heap[idx], heap[largestIdx]);
            sinkDown(largestIdx);
        }
    }
};
package main

import "math"

type MaxHeap struct {
    heap []int
}

func NewMaxHeap() *MaxHeap {
    return &MaxHeap{heap: make([]int, 0)}
}

func (h *MaxHeap) Insert(val int) {
    h.heap = append(h.heap, val)
    h.bubbleUp(len(h.heap) - 1)
}

func (h *MaxHeap) ExtractMax() int {
    if len(h.heap) == 1 {
        val := h.heap[0]
        h.heap = h.heap[:0]
        return val
    }
    if len(h.heap) == 0 {
        return math.MinInt
    }

    max := h.heap[0]
    h.heap[0] = h.heap[len(h.heap)-1]
    h.heap = h.heap[:len(h.heap)-1]
    h.sinkDown(0)
    return max
}

func (h *MaxHeap) Peek() int {
    if len(h.heap) == 0 {
        return math.MinInt
    }
    return h.heap[0]
}

func (h *MaxHeap) Size() int {
    return len(h.heap)
}

func (h *MaxHeap) bubbleUp(idx int) {
    parentIdx := (idx - 1) / 2
    if parentIdx >= 0 && h.heap[idx] > h.heap[parentIdx] {
        h.heap[idx], h.heap[parentIdx] = h.heap[parentIdx], h.heap[idx]
        h.bubbleUp(parentIdx)
    }
}

func (h *MaxHeap) sinkDown(idx int) {
    leftIdx := 2*idx + 1
    rightIdx := 2*idx + 2
    largestIdx := idx

    if leftIdx < len(h.heap) && h.heap[leftIdx] > h.heap[largestIdx] {
        largestIdx = leftIdx
    }
    if rightIdx < len(h.heap) && h.heap[rightIdx] > h.heap[largestIdx] {
        largestIdx = rightIdx
    }

    if largestIdx != idx {
        h.heap[idx], h.heap[largestIdx] = h.heap[largestIdx], h.heap[idx]
        h.sinkDown(largestIdx)
    }
}
class MaxHeap
    def initialize
        @heap = []
    end

    def insert(val)
        @heap << val
        bubble_up(@heap.length - 1)
    end

    def extract_max
        return @heap.pop if @heap.length == 1
        return nil if @heap.empty?

        max = @heap[0]
        @heap[0] = @heap.pop
        sink_down(0)
        max
    end

    def peek
        @heap[0] if @heap.any?
    end

    def size
        @heap.length
    end

    private

    def bubble_up(idx)
        parent_idx = (idx - 1) / 2
        if parent_idx >= 0 && @heap[idx] > @heap[parent_idx]
            @heap[idx], @heap[parent_idx] = @heap[parent_idx], @heap[idx]
            bubble_up(parent_idx)
        end
    end

    def sink_down(idx)
        left_idx = 2 * idx + 1
        right_idx = 2 * idx + 2
        largest_idx = idx

        if left_idx < @heap.length && @heap[left_idx] > @heap[largest_idx]
            largest_idx = left_idx
        end
        if right_idx < @heap.length && @heap[right_idx] > @heap[largest_idx]
            largest_idx = right_idx
        end

        if largest_idx != idx
            @heap[idx], @heap[largest_idx] = @heap[largest_idx], @heap[idx]
            sink_down(largest_idx)
        end
    end
end

Code Breakdown

Key Variables and Their Roles

  • heap: Array storing the complete binary tree representation
  • size: Current number of elements in the heap
  • idx: Current position being processed in bubble up/sink down operations
  • parentIdx: Index of parent node: (idx - 1) / 2
  • leftIdx: Index of left child: 2 * idx + 1
  • rightIdx: Index of right child: 2 * idx + 2

Critical Sections

  1. Initialization: Create empty array to store heap elements
  2. Expansion (Insert): Add element to end, then bubble up to maintain heap property
  3. Contraction (Extract): Replace root with last element, then sink down to restore heap property

Algorithm Flow 

  graph TD
    A[Insert Operation] --> B[Add to end of array]
    B --> C[Bubble up if needed]
    C --> D[Maintain heap property]

    E[Extract Operation] --> F[Remove root]
    F --> G[Move last element to root]
    G --> H[Sink down if needed]
    H --> I[Maintain heap property]

Variations

Min-Heap Implementation

To convert the above to a min-heap, simply change the comparison operators:

  • In _bubbleUp: Change > to <
  • In _sinkDown: Change > to <

Priority Queue with Custom Comparator 

class PriorityQueue {
    constructor(comparator = (a, b) => a - b) {
        this.heap = [];
        this.comparator = comparator; // Returns negative if a < b
    }

    push(val) {
        this.heap.push(val);
        this._bubbleUp(this.heap.length - 1);
    }

    pop() {
        if (this.heap.length === 1) return this.heap.pop();
        if (this.heap.length === 0) return null;

        const root = this.heap[0];
        this.heap[0] = this.heap.pop();
        this._sinkDown(0);
        return root;
    }

    peek() {
        return this.heap.length > 0 ? this.heap[0] : null;
    }

    isEmpty() {
        return this.heap.length === 0;
    }

    _bubbleUp(idx) {
        const parentIdx = Math.floor((idx - 1) / 2);
        if (parentIdx >= 0 && this.comparator(this.heap[idx], this.heap[parentIdx]) < 0) {
            [this.heap[idx], this.heap[parentIdx]] = [this.heap[parentIdx], this.heap[idx]];
            this._bubbleUp(parentIdx);
        }
    }

    _sinkDown(idx) {
        const leftIdx = 2 * idx + 1;
        const rightIdx = 2 * idx + 2;
        let bestIdx = idx;

        if (leftIdx < this.heap.length && this.comparator(this.heap[leftIdx], this.heap[bestIdx]) < 0) {
            bestIdx = leftIdx;
        }
        if (rightIdx < this.heap.length && this.comparator(this.heap[rightIdx], this.heap[bestIdx]) < 0) {
            bestIdx = rightIdx;
        }

        if (bestIdx !== idx) {
            [this.heap[idx], this.heap[bestIdx]] = [this.heap[bestIdx], this.heap[idx]];
            this._sinkDown(bestIdx);
        }
    }
}
import heapq

class PriorityQueue:
    def __init__(self, comparator=None):
        self.heap = []
        self.comparator = comparator

    def push(self, val):
        if self.comparator:
            heapq.heappush(self.heap, (self.comparator(val), val))
        else:
            heapq.heappush(self.heap, val)

    def pop(self):
        if self.comparator:
            return heapq.heappop(self.heap)[1]
        else:
            return heapq.heappop(self.heap)

    def peek(self):
        if self.comparator:
            return self.heap[0][1] if self.heap else None
        else:
            return self.heap[0] if self.heap else None

    def is_empty(self):
        return len(self.heap) == 0
import java.util.PriorityQueue;
import java.util.Comparator;

public class PriorityQueue<T> {
    private PriorityQueue<T> heap;

    public PriorityQueue() {
        this.heap = new PriorityQueue<>();
    }

    public PriorityQueue(Comparator<T> comparator) {
        this.heap = new PriorityQueue<>(comparator);
    }

    public void push(T val) {
        heap.offer(val);
    }

    public T pop() {
        return heap.poll();
    }

    public T peek() {
        return heap.peek();
    }

    public boolean isEmpty() {
        return heap.isEmpty();
    }
}
#include <queue>
#include <functional>

template<typename T, typename Compare = std::less<T>>
class PriorityQueue {
private:
    std::priority_queue<T, std::vector<T>, Compare> heap;

public:
    void push(const T& val) {
        heap.push(val);
    }

    T pop() {
        T val = heap.top();
        heap.pop();
        return val;
    }

    T peek() {
        return heap.top();
    }

    bool empty() {
        return heap.empty();
    }
};
package main

import "container/heap"

type PriorityQueue struct {
    items []int
    minHeap bool
}

func NewPriorityQueue(minHeap bool) *PriorityQueue {
    return &PriorityQueue{
        items: make([]int, 0),
        minHeap: minHeap,
    }
}

func (pq *PriorityQueue) Push(val int) {
    pq.items = append(pq.items, val)
    pq.bubbleUp(len(pq.items) - 1)
}

func (pq *PriorityQueue) Pop() int {
    if len(pq.items) == 0 {
        return 0
    }

    val := pq.items[0]
    pq.items[0] = pq.items[len(pq.items)-1]
    pq.items = pq.items[:len(pq.items)-1]
    pq.sinkDown(0)
    return val
}

func (pq *PriorityQueue) Peek() int {
    if len(pq.items) == 0 {
        return 0
    }
    return pq.items[0]
}

func (pq *PriorityQueue) bubbleUp(idx int) {
    parentIdx := (idx - 1) / 2
    if parentIdx >= 0 {
        shouldSwap := false
        if pq.minHeap {
            shouldSwap = pq.items[idx] < pq.items[parentIdx]
        } else {
            shouldSwap = pq.items[idx] > pq.items[parentIdx]
        }

        if shouldSwap {
            pq.items[idx], pq.items[parentIdx] = pq.items[parentIdx], pq.items[idx]
            pq.bubbleUp(parentIdx)
        }
    }
}

func (pq *PriorityQueue) sinkDown(idx int) {
    leftIdx := 2*idx + 1
    rightIdx := 2*idx + 2
    targetIdx := idx

    if leftIdx < len(pq.items) {
        if pq.minHeap {
            if pq.items[leftIdx] < pq.items[targetIdx] {
                targetIdx = leftIdx
            }
        } else {
            if pq.items[leftIdx] > pq.items[targetIdx] {
                targetIdx = leftIdx
            }
        }
    }

    if rightIdx < len(pq.items) {
        if pq.minHeap {
            if pq.items[rightIdx] < pq.items[targetIdx] {
                targetIdx = rightIdx
            }
        } else {
            if pq.items[rightIdx] > pq.items[targetIdx] {
                targetIdx = rightIdx
            }
        }
    }

    if targetIdx != idx {
        pq.items[idx], pq.items[targetIdx] = pq.items[targetIdx], pq.items[idx]
        pq.sinkDown(targetIdx)
    }
}
class PriorityQueue
    def initialize(comparator = ->(a, b) { a <=> b })
        @heap = []
        @comparator = comparator
    end

    def push(val)
        @heap << val
        bubble_up(@heap.length - 1)
    end

    def pop
        return @heap.pop if @heap.length == 1
        return nil if @heap.empty?

        root = @heap[0]
        @heap[0] = @heap.pop
        sink_down(0)
        root
    end

    def peek
        @heap[0] if @heap.any?
    end

    def empty?
        @heap.empty?
    end

    private

    def bubble_up(idx)
        parent_idx = (idx - 1) / 2
        if parent_idx >= 0 && @comparator.call(@heap[idx], @heap[parent_idx]) < 0
            @heap[idx], @heap[parent_idx] = @heap[parent_idx], @heap[idx]
            bubble_up(parent_idx)
        end
    end

    def sink_down(idx)
        left_idx = 2 * idx + 1
        right_idx = 2 * idx + 2
        best_idx = idx

        if left_idx < @heap.length && @comparator.call(@heap[left_idx], @heap[best_idx]) < 0
            best_idx = left_idx
        end
        if right_idx < @heap.length && @comparator.call(@heap[right_idx], @heap[best_idx]) < 0
            best_idx = right_idx
        end

        if best_idx != idx
            @heap[idx], @heap[best_idx] = @heap[best_idx], @heap[idx]
            sink_down(best_idx)
        end
    end
end

Practice

Ready to apply these templates? Head to our Practice Problems page to work through real coding challenges that use these heap and priority queue patterns.

Pro Tip: When implementing heaps from scratch, always double-check your parent/child index calculations. The most common bug is off-by-one errors in the bubble up and sink down operations.