Heap & Priority Queue: Complete Guide with Examples

A heap always knows which element is the most important. In a min-heap, that element is the smallest value in the collection. In a max-heap, it is the largest. Inserting a new element and removing the extreme both cost

The questions a heap answers show up constantly in coding interviews. Finding the k largest numbers in a stream, merging k sorted lists, and keeping a running median all need the current extreme value on demand. Each of those problems has a clean heap solution, and interviewers use them because the pattern recognition matters as much as the code itself.

Definition: a heap is a complete binary tree stored in a plain array. Every parent has a fixed relationship with its children. In a min-heap, each parent is smaller than its children. In a max-heap, each parent is larger. The parent of index i sits at index (i-1)/2, and the children sit at 2i+1 and 2i+2. A priority queue is the interface built on top of a heap. You push an item with a priority, and the item with the highest priority is what the pop operation returns.

Real-World Analogy

In an emergency room, the patient in the worst condition is treated first, not the patient who arrived first. When a new patient comes in, the nurse fits them into the queue by severity. The queue is not fully sorted. The only requirement is that the sickest patient is always at the front, ready to be taken next.

That is the whole job of a heap. It keeps one extreme element at the root and does not bother ordering the rest. A fully sorted list can find its extreme in

Visual Explanation

Here is what happens when a value is inserted into a min-heap. The value is appended at the bottom of the tree, then it walks upward while it is smaller than its parent. Each swap moves the violation one level closer to the root.

    graph TD
    A["Insert 3 into [4, 8, 5, 9, 10]"] --> B["Append 3 at the end"]
    B --> C["3 sits below 5"]
    C --> D{"Is 3 smaller than its parent?"}
    D -->|Yes| E["Swap 3 with its parent"]
    E --> F{"Is 3 smaller than the new parent?"}
    F -->|Yes| E
    F -->|No| G["Heap property restored"]
    D -->|No| G
  

The same heap looks like two different things at once. As a tree, it is a filled, level-by-level shape. As an array, it is a flat list where the indexing formulas locate relatives without any pointers.

    graph TD
    subgraph "Tree form"
        T1["3"] --> T2["8"]
        T1 --> T3["4"]
        T2 --> T4["9"]
        T2 --> T5["10"]
        T3 --> T6["5"]
    end
    subgraph "Array form"
        A["3, 8, 4, 9, 10, 5"]
    end
  

Two details matter here. The heap is stored in a flat array, so there are no pointers and no wasted memory between nodes. Each insert touches only one path from a leaf to the root. Because the tree is complete, that path has length

When to Use This Pattern

These are the problem shapes that should make you reach for a heap.

• You need the k largest or k smallest elements and k is small compared to the input size. If k is close to the size of the input, a full sort is simpler and the heap buys you nothing.
• The data arrives one element at a time, and you need the current extreme or the current kth extreme after every arrival. Streams and live feeds look exactly like this.
• You have several sorted sequences and need to merge them by repeatedly picking the smallest remaining head.
• The problem asks for a median or another order statistic that shifts as the dataset changes.
• You are implementing an algorithm that repeatedly picks the best available candidate, like Dijkstra’s algorithm or a task scheduler.

Complexity Analysis

The heap operations have these costs:

The push and pop costs come from the tree height. A complete binary tree with N nodes has a height of about log2(N), and every insert or extract touches exactly one path of that length. Heapify is cheaper than inserting N elements one at a time, which costs

The patterns on this page inherit these costs. Top-K with a heap capped at size k costs

Common Mistakes

These errors all share a root cause: losing track of what the root is supposed to represent.

Choosing the wrong heap type. Python’s heapq is a min-heap, and there is no max-heap in the standard library. Candidates who learned heaps in C++ reach for the top of a Python heap when they need the maximum, and get the minimum instead. The fix is to negate values when pushing and negate again when reading, or to write an explicit comparator where the language allows one. Before writing any code, say out loud which extreme needs to sit at the root. That one sentence prevents most heap bugs.

Breaking the size cap in top-K problems. The top-K template keeps the heap at exactly k elements. Pushing without popping lets the heap grow to N, and the root stops being the kth extreme. It becomes the global extreme, which is a different answer. Catch this by tracing the invariant after every insert with a small input, like k=2 and the values 1, 5, 3. After the third insert the root must be 3, the 2nd largest of what has been seen.

Getting the sign of the comparator backwards. Languages disagree about their defaults. C++ priority_queue is a max-heap. Java’s PriorityQueue is a min-heap. Go’s container/heap follows whatever your Less function says. When you write a comparator, check it against a two-element input instead of trusting the name. A related variant is negating in Python and then forgetting to negate when reading the answer. That produces the mirror of the intended result, which is easy to miss because the code still runs.

Letting the two median heaps drift out of balance. The running median keeps the lower half in a max-heap and the upper half in a min-heap, and their sizes may differ by at most one. If you push into both without rebalancing, the median read picks a value that is not in the middle of the data. Test with both an even and an odd number of insertions, because the median formula changes between the two cases.

Related Patterns

• Greedy Algorithms . Many greedy strategies need the best remaining candidate on demand, and a heap supplies it in
  O(log N)
  per step. Task scheduling problems sit exactly on the boundary between the two patterns.
• Shortest Path . Dijkstra’s algorithm is a priority queue in disguise. Each relaxation pushes a better distance into the heap, so the heap picks the next unvisited node.
• Divide and Conquer . The kth largest element can also be found with quickselect. The heap approach gives guaranteed
  O(N log k)
  time, while quickselect gives expected
  O(N)
  with a worse worst case.

Next Steps

Once the concept is clear, the next step is making the code automatic. Check out the code templates for memorizable implementations in 6 languages, then work through the practice problems to apply the pattern to real interview questions.