Heap & Priority Queue: Code Templates in 6 Languages

Coding Patterns - Guide to 30 Core Algorithm Patterns

Heap & Priority Queue: Complete Guide with Examples

If you have not read the concept guide yet, start there for the intuition and complexity analysis. This page gives you the code to memorize and adapt during an interview. Every template below runs a heap of size k or smaller, so the time is

O(N log k)

or better unless otherwise noted.

The Heap Helpers for JavaScript and Ruby

Python, Java, C++, and Go ship a heap in the standard library, so those tabs use the built-ins directly. JavaScript and Ruby do not, so every JavaScript and Ruby tab on this page uses one of the helper classes below. The helper takes a less function that decides which of two values outranks the other. The default is a min-heap, where smaller values rank higher.

class Heap {
    constructor(values = [], less = (a, b) => a < b) {
        this.less = less;
        this.items = values.slice();
        // batch construction sinks every non-leaf once.
        // doing it this way costs O(N) instead of O(N log N)
        for (let i = Math.floor(this.items.length / 2) - 1; i >= 0; i--) {
            this._sink(i);
        }
    }

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

    peek() {
        return this.items[0];
    }

    push(value) {
        this.items.push(value);
        this._rise(this.items.length - 1);
    }

    pop() {
        if (this.items.length === 1) return this.items.pop();
        const top = this.items[0];
        // move the last element to the root, then sink the
        // new root back into a valid position
        this.items[0] = this.items.pop();
        this._sink(0);
        return top;
    }

    // a freshly appended element walks toward the root while
    // it outranks its parent
    _rise(i) {
        while (i > 0) {
            const parent = (i - 1) >> 1;
            if (!this.less(this.items[i], this.items[parent])) break;
            [this.items[i], this.items[parent]] = [this.items[parent], this.items[i]];
            i = parent;
        }
    }

    // the root replacement walks down while a child outranks it
    _sink(i) {
        const n = this.items.length;
        while (true) {
            let best = i;
            const left = 2 * i + 1;
            const right = 2 * i + 2;
            if (left < n && this.less(this.items[left], this.items[best])) best = left;
            if (right < n && this.less(this.items[right], this.items[best])) best = right;
            if (best === i) break;
            [this.items[i], this.items[best]] = [this.items[best], this.items[i]];
            i = best;
        }
    }
}

class Heap
    def initialize(values = [], &less)
        @less = less || ->(a, b) { a < b }
        @items = values.dup
        # batch construction sinks every non-leaf once.
        # doing it this way costs O(N) instead of O(N log N)
        (@items.length / 2 - 1).downto(0) { |i| sink(i) }
    end

    def size
        @items.length
    end

    def peek
        @items[0]
    end

    def push(value)
        @items << value
        rise(@items.length - 1)
    end

    def pop
        return @items.pop if @items.length == 1
        top = @items[0]
        # move the last element to the root, then sink the
        # new root back into a valid position
        @items[0] = @items.pop
        sink(0)
        top
    end

    private

    # a freshly appended element walks toward the root while
    # it outranks its parent
    def rise(i)
        while i > 0
            parent = (i - 1) / 2
            break unless @less.call(@items[i], @items[parent])
            @items[i], @items[parent] = @items[parent], @items[i]
            i = parent
        end
    end

    # the root replacement walks down while a child outranks it
    def sink(i)
        n = @items.length
        loop do
            best = i
            left = 2 * i + 1
            right = 2 * i + 2
            best = left if left < n && @less.call(@items[left], @items[best])
            best = right if right < n && @less.call(@items[right], @items[best])
            break if best == i
            @items[i], @items[best] = @items[best], @items[i]
            i = best
        end
    end
end

Main Template: Top-K with a Size-k Min-Heap

The most common heap problem is finding the k largest or k smallest elements. The trick is a min-heap capped at size k. Push every element, and pop whenever the heap exceeds k. The root is then the kth largest of everything seen so far, because every element that got popped was the smallest of a set of k+1 elements that all arrived before the final answer could be known.

Use this for Kth Largest Element in a Stream and Kth Largest Element in an Array .

function topK(nums, k) {
    // a min-heap of size k keeps the k largest values.
    // the root is the smallest of those k, so it is the
    // element that must leave when a larger one arrives
    const heap = new Heap();
    for (const num of nums) {
        heap.push(num);
        if (heap.size() > k) {
            heap.pop();
        }
    }
    const result = [];
    while (heap.size() > 0) {
        result.push(heap.pop());
    }
    return result;
}

import heapq

def top_k(nums, k):
    # heapq is a min-heap. capped at size k, its root is
    # the smallest of the k largest values seen so far.
    heap = []
    for num in nums:
        heapq.heappush(heap, num)
        if len(heap) > k:
            heapq.heappop(heap)
    return heap

import java.util.PriorityQueue;
import java.util.ArrayList;
import java.util.List;

public List<Integer> topK(int[] nums, int k) {
    // the default PriorityQueue is a min-heap. capped at
    // size k, the root is the kth largest value so far.
    PriorityQueue<Integer> heap = new PriorityQueue<>();
    for (int num : nums) {
        heap.offer(num);
        if (heap.size() > k) {
            heap.poll();
        }
    }
    return new ArrayList<>(heap);
}

#include <vector>
#include <queue>
#include <functional>

vector<int> topK(vector<int>& nums, int k) {
    // greater<int> turns the default max-heap into a
    // min-heap, so the root is the smallest of the k
    // largest values seen so far
    priority_queue<int, vector<int>, greater<int>> heap;
    for (int num : nums) {
        heap.push(num);
        if (heap.size() > k) {
            heap.pop();
        }
    }
    vector<int> result;
    while (!heap.empty()) {
        result.push_back(heap.top());
        heap.pop();
    }
    return result;
}

package main

import "container/heap"

func topK(nums []int, k int) []int {
    h := &IntMinHeap{}
    heap.Init(h)
    for _, num := range nums {
        heap.Push(h, num)
        if h.Len() > k {
            heap.Pop(h)
        }
    }
    result := make([]int, 0, k)
    for h.Len() > 0 {
        result = append(result, heap.Pop(h).(int))
    }
    return result
}

type IntMinHeap []int

func (h IntMinHeap) Len() int           { return len(h) }
func (h IntMinHeap) Less(i, j int) bool { return h[i] < h[j] }
func (h IntMinHeap) Swap(i, j int)      { h[i], h[j] = h[j], h[i] }

func (h *IntMinHeap) Push(x interface{}) {
    *h = append(*h, x.(int))
}

func (h *IntMinHeap) Pop() interface{} {
    old := *h
    n := len(old)
    x := old[n-1]
    *h = old[:n-1]
    return x
}

def top_k(nums, k)
    # a min-heap capped at size k keeps the k largest
    # values. the root is the one that must leave when a
    # larger value arrives.
    heap = Heap.new
    nums.each do |num|
        heap.push(num)
        heap.pop if heap.size > k
    end

    result = []
    result << heap.pop while heap.size > 0
    result
end

Templates only help if you can recall them without staring at the screen. Turn these snippets into flashcards for daily mobile review.

Code Breakdown

Key Variables

heap (or h): the priority queue, always kept at size k or smaller.
k: how many extreme elements to keep. The cap is the whole point of the template.
root / top: the smallest of the k largest values. It is the value that leaves when a bigger value arrives, which is why a min-heap is the right shape for top-K.

Visual Mechanism

    graph TD
    A["Next input value"] --> B["Push into the min-heap"]
    B --> C{"Heap size > k?"}
    C -->|Yes| D["Pop the root"]
    C -->|No| E["Keep the value"]
    D --> E
    E --> F["Root is the kth largest so far"]

Critical Sections

The push is a normal heap insert at

O(log k)

. The heap never exceeds size k, so the cost of every operation depends on k, not on N.

The cap check is the section that makes the template correct. After every push, if the heap holds more than k elements, pop. The popped value is the smallest of the current k+1, so it cannot be part of the final answer. Skipping this check turns the heap into a full min-heap whose root is the global minimum, which is a completely different answer.

The peek is a free read. The root always holds the kth largest, so the answer is available at any moment, not just at the end. That property is what makes the template work for streaming input.

Variations

1. Max-Heap for k Smallest

The mirror image of the main template. To keep the k smallest values, use a max-heap capped at k. The root is the largest of the k smallest, so it is the one that leaves when a smaller value arrives.

import heapq

def smallest_k(nums, k):
    # heapq is a min-heap, so negate every value. the root
    # is then the largest of the k smallest values and the
    # one that must leave when a smaller value arrives.
    heap = []
    for num in nums:
        heapq.heappush(heap, -num)
        if len(heap) > k:
            heapq.heappop(heap)
    return [-x for x in heap]

import java.util.PriorityQueue;
import java.util.Collections;
import java.util.ArrayList;
import java.util.List;

public List<Integer> smallestK(int[] nums, int k) {
    // reverseOrder turns the default min-heap into a
    // max-heap, so the root is the largest of the k
    // smallest values
    PriorityQueue<Integer> heap = new PriorityQueue<>(Collections.reverseOrder());
    for (int num : nums) {
        heap.offer(num);
        if (heap.size() > k) {
            heap.poll();
        }
    }
    return new ArrayList<>(heap);
}

#include <vector>
#include <queue>

vector<int> smallestK(vector<int>& nums, int k) {
    // the default priority_queue is already a max-heap,
    // so no comparator is needed here
    priority_queue<int> heap;
    for (int num : nums) {
        heap.push(num);
        if (heap.size() > k) {
            heap.pop();
        }
    }
    vector<int> result;
    while (!heap.empty()) {
        result.push_back(heap.top());
        heap.pop();
    }
    return result;
}

package main

import "container/heap"

func smallestK(nums []int, k int) []int {
    h := &IntMaxHeap{}
    heap.Init(h)
    for _, num := range nums {
        heap.Push(h, num)
        if h.Len() > k {
            heap.Pop(h)
        }
    }
    result := make([]int, 0, k)
    for h.Len() > 0 {
        result = append(result, heap.Pop(h).(int))
    }
    return result
}

type IntMaxHeap []int

func (h IntMaxHeap) Len() int           { return len(h) }
func (h IntMaxHeap) Less(i, j int) bool { return h[i] > h[j] }
func (h IntMaxHeap) Swap(i, j int)      { h[i], h[j] = h[j], h[i] }

func (h *IntMaxHeap) Push(x interface{}) {
    *h = append(*h, x.(int))
}

func (h *IntMaxHeap) Pop() interface{} {
    old := *h
    n := len(old)
    x := old[n-1]
    *h = old[:n-1]
    return x
}

The JavaScript and Ruby helpers from the top of this page make the same flip with a one-line comparator: new Heap([], (a, b) => a > b) in JavaScript and Heap.new { |a, b| a > b } in Ruby.

2. Two Heaps for a Running Median

Keep the lower half of the data in a max-heap and the upper half in a min-heap. Each insert pushes into the lower half, moves the largest lower value into the upper half, then rebalances so the lower half holds the extra element when the count is odd. The median is then a root read.

Use this for Find Median from Data Stream .

class MedianFinder {
    constructor() {
        // low is a max-heap, high is a min-heap
        this.low = new Heap([], (a, b) => a > b);
        this.high = new Heap();
    }

    addNum(num) {
        // push into low, then move low's largest into high.
        // this keeps every low value below every high value
        this.low.push(num);
        this.high.push(this.low.pop());
        // low holds the extra element when the count is odd
        if (this.low.size() < this.high.size()) {
            this.low.push(this.high.pop());
        }
    }

    findMedian() {
        if (this.low.size() > this.high.size()) {
            return this.low.peek();
        }
        return (this.low.peek() + this.high.peek()) / 2;
    }
}

import heapq

class MedianFinder:
    def __init__(self):
        # low is a max-heap over negated values, high is a
        # min-heap. every low value stays at or below every
        # high value.
        self.low = []
        self.high = []

    def add_num(self, num):
        # push into low, then move low's largest value into
        # high. this keeps the ordering invariant between
        # the two halves.
        heapq.heappush(self.low, -num)
        heapq.heappush(self.high, -heapq.heappop(self.low))
        # low holds the extra element when the count is odd
        if len(self.low) < len(self.high):
            heapq.heappush(self.low, -heapq.heappop(self.high))

    def find_median(self):
        if len(self.low) > len(self.high):
            return -self.low[0]
        return (-self.low[0] + self.high[0]) / 2

The rebalance step runs after every insert, not just sometimes. Skipping it lets the two halves drift, and the median read starts picking values from the wrong side of the split.

3. K-Way Merge with a Min-Heap

When k sorted lists need to merge into one, push the head of every list into a min-heap. Pop the smallest head, append it to the result, and push the next node from that same list. The heap never holds more than k nodes.

Use this for Merge k Sorted Lists .

function mergeKLists(lists) {
    // min-heap of list nodes ordered by value. each list
    // contributes its current head; popping a head reveals
    // the next node of that same list.
    const heap = new Heap([], (a, b) => a.val < b.val);
    for (const head of lists) {
        if (head) heap.push(head);
    }

    const dummy = { val: 0, next: null };
    let current = dummy;
    while (heap.size() > 0) {
        current.next = heap.pop();
        current = current.next;
        if (current.next) {
            heap.push(current.next);
        }
    }
    return dummy.next;
}

import heapq

def merge_k_lists(lists):
    # the list index breaks ties between equal values,
    # because heap elements need a total order
    heap = []
    for i, head in enumerate(lists):
        if head:
            heapq.heappush(heap, (head.val, i, head))

    dummy = ListNode()
    current = dummy
    while heap:
        _, i, node = heapq.heappop(heap)
        current.next = node
        current = current.next
        if node.next:
            heapq.heappush(heap, (node.next.val, i, node.next))
    return dummy.next

The heap size stays at k, so each push and pop costs

O(log k)

. With N total nodes, the merge runs in

O(N log k)

time.

4. Heapify an Existing Array

Building a heap from an existing array costs

O(N)

when done in one batch, not

O(N log N)

. Pushing N elements one at a time pays the full log cost for each one. The batch pass sinks every non-leaf exactly once, and most nodes are near the bottom where a sink costs a step or two.

import heapq

heap = nums
heapq.heapify(heap)

Java and C++ do not expose a batch heapify on their standard heaps, so they build by pushing, which is

O(N log N)

. The Go helper in the main template also heapifies in the constructor, which is why its batch construction comment calls out the

O(N)

cost.

Each variation above is a separate review card in the app. Drill them individually so you do not mix up the conditions under pressure.

Now head to the practice problems to apply these templates to real interview questions.

Now that you have the templates, the next step is application. Head to the practice problems or start reviewing these templates with spaced repetition .