Heaps

Updated Nov 16, 2026 · 5 min read
On this page

    "Give me the 10 most frequent words", "merge these k sorted lists", "schedule the next task that's due": each asks for the smallest or largest item, over and over, while new items keep arriving. Sorting everything after each change is O(n log n) each time; scanning for the minimum is O(n). A heap gives you the minimum in O(1) and handles each insert or removal in O(log n).

    How it works

    A tree with one rule, stored in an array

    In a min-heap every parent is at most its children, so the smallest value is at the root; the tree is stored level by level in an array.
    In a min-heap every parent is at most its children, so the smallest value is at the root; the tree is stored level by level in an array.

    A min-heap is a binary tree where every parent is less than or equal to its children. That's a much weaker rule than a BST: siblings can be in any order, and the heap isn't sorted. But it guarantees the smallest element is always at the root. A max-heap is the same with "greater than or equal".

    A heap is always a complete tree: every level is full except the last, which fills from the left. That lets it live in a plain array with no pointers:

    • children of index i are at 2i + 1 and 2i + 2
    • the parent of index i is at (i − 1) // 2

    Push: add at the end, sift up

    A new value goes in the next free slot, then swaps with its parent while it is smaller; at most one swap per level.
    A new value goes in the next free slot, then swaps with its parent while it is smaller; at most one swap per level.

    To push, append the value at the end of the array, then compare it with its parent and swap while it's smaller. To pop the minimum, take the root, move the last element to the root, and sift it down: swap it with its smaller child until neither child is smaller. Both walk one root-to-leaf path, so they cost O(log n).

    Building a heap from an existing array of n items (heapify) takes O(n), not O(n log n), because most nodes sit near the bottom and barely move.

    In your language

    • Python heapq is a min-heap on a list: heappush, heappop, heapify, heap[0] to peek. For a max-heap, push negated values.
    • Java PriorityQueue is a min-heap by default; pass Collections.reverseOrder() or a comparator for a max-heap.
    • C++ priority_queue is a max-heap by default; use priority_queue<int, vector<int>, greater<int>> for a min-heap.
    • Go container/heap needs a type that implements five methods (Len, Less, Swap, Push, Pop).

    Operations and costs

    OperationCost
    Peek at min (or max)O(1)
    PushO(log n)
    Pop min (or max)O(log n)
    Build from n items (heapify)O(n)
    Search for an arbitrary valueO(n)
    Remove an arbitrary valueO(n) to find it (unless you track positions)

    When to reach for it

    • Top K or K-th largest/smallest: keep a heap of size k. For the k largest, use a min-heap: its top is the weakest of your current best k, so any new value that beats it replaces it. Cost O(n log k), and memory O(k).
    • Merge k sorted lists or streams: keep one candidate from each list in a min-heap; pop the smallest and push its successor. O(N log k) for N total items.
    • Scheduling: always run the next task by deadline, priority or end time (meeting rooms, task scheduler, CPU scheduling).
    • Running median: two heaps, a max-heap for the lower half and a min-heap for the upper half.
    • Shortest paths with weights: Dijkstra's algorithm pops the closest unvisited node from a min-heap.
    To keep the 3 largest values of a stream, keep a min-heap of size 3 and replace its top whenever a larger value arrives.
    To keep the 3 largest values of a stream, keep a min-heap of size 3 and replace its top whenever a larger value arrives.

    Example

    Return the k largest values from a list, largest first, using a size-k min-heap.

    import heapq
    
    def k_largest(nums, k):
        heap = []
        for x in nums:
            if len(heap) < k:
                heapq.heappush(heap, x)
            elif x > heap[0]:
                heapq.heapreplace(heap, x)   # pop the smallest, push x
        return sorted(heap, reverse=True)
    List<Integer> kLargest(int[] nums, int k) {
        PriorityQueue<Integer> heap = new PriorityQueue<>(); // min-heap
        for (int x : nums) {
            if (heap.size() < k) {
                heap.offer(x);
            } else if (x > heap.peek()) {
                heap.poll();
                heap.offer(x);
            }
        }
        List<Integer> out = new ArrayList<>(heap);
        out.sort(Collections.reverseOrder());
        return out;
    }
    vector<int> kLargest(const vector<int>& nums, int k) {
        priority_queue<int, vector<int>, greater<int>> heap;  // min-heap
        for (int x : nums) {
            if ((int)heap.size() < k) {
                heap.push(x);
            } else if (x > heap.top()) {
                heap.pop();
                heap.push(x);
            }
        }
        vector<int> out;
        while (!heap.empty()) { out.push_back(heap.top()); heap.pop(); }
        reverse(out.begin(), out.end());
        return out;
    }
    type MinHeap []int
    
    func (h MinHeap) Len() int            { return len(h) }
    func (h MinHeap) Less(i, j int) bool  { return h[i] < h[j] }
    func (h MinHeap) Swap(i, j int)       { h[i], h[j] = h[j], h[i] }
    func (h *MinHeap) Push(x interface{}) { *h = append(*h, x.(int)) }
    func (h *MinHeap) Pop() interface{} {
        old := *h
        x := old[len(old)-1]
        *h = old[:len(old)-1]
        return x
    }
    
    func kLargest(nums []int, k int) []int {
        h := &MinHeap{}
        for _, x := range nums {
            if h.Len() < k {
                heap.Push(h, x)
            } else if x > (*h)[0] {
                heap.Pop(h)
                heap.Push(h, x)
            }
        }
        out := make([]int, h.Len())
        for i := len(out) - 1; i >= 0; i-- {
            out[i] = heap.Pop(h).(int)
        }
        return out
    }

    Time: O(n log k). Space: O(k). With [5, 1, 9, 3, 7, 2, 8] and k = 3, the heap ends as {7, 8, 9} and the result is [9, 8, 7].

    Common mistakes

    • Wrong heap direction. For the k largest, you want a min-heap of size k (so you can evict the smallest of them). Many people reach for a max-heap of everything, which is O(n log n) and O(n) memory.
    • Forgetting language defaults. C++ is max-heap by default, Python and Java are min-heap.
    • Assuming a heap is sorted. Only the top is guaranteed; iterating over the array doesn't give sorted order.
    • Comparing tuples with uncomparable parts. In Python, (priority, node) fails if two priorities tie and nodes can't be compared; add a counter as a tie-breaker: (priority, count, node).
    • Removing arbitrary items. Heaps can't do this efficiently. Use lazy deletion (mark as removed and skip when popped) or a balanced tree.

    Say this in the interview

    • "I only need the k largest, so I'll keep a min-heap of size k; its top is the smallest of my current top k. That's O(n log k) instead of sorting at O(n log n)."
    • "Push and pop are O(log n) because they walk one path of a complete tree."
    • "For the median I'll keep two heaps: a max-heap for the lower half and a min-heap for the upper half, balanced to within one element."

    Used in