Heap priority queue explained

Most engineers think of a heap as a tree. Draw a triangle on a whiteboard, label the nodes, done. That mental picture is technically correct and practically useless. To get the heap priority queue explained properly, you need to start with the array. The heap's entire power comes from the fact that it isn't stored as a tree. It's a flat array with a mathematical trick that makes tree navigation free. Once you see the array representation clearly, every heap operation becomes a predictable sequence of swaps, and the "priority queue" label stops feeling like a separate concept.

Heap priority queue explained: The core data structure

A heap is a complete binary tree where every parent node satisfies an ordering constraint relative to its children. In a min-heap, every parent is smaller than or equal to both children. In a max-heap, every parent is larger. This is the heap property, and it's the only structural rule that matters.

That single rule does all the work.

In practice, the heap lives as a flat array. For any element at index i, its left child sits at 2i + 1, its right child at 2i + 2, and its parent at (i - 1) / 2 using integer division. No pointers and no node objects. The completeness guarantee means there are no gaps in the array, with every level full except possibly the last, which fills left to right.

The array representation isn't a compromise. It's the reason heaps are fast. Pointer-based trees require memory allocation per node and cache-unfriendly traversal. An array-based heap sits in contiguous memory, and navigating from parent to child costs one multiplication and one addition. For a heap with a million elements, the maximum depth is 20 levels. Every insert and every extraction touches at most 20 elements.

The distinction between min-heap and max-heap is only which direction the ordering goes. Every algorithm works identically. If you understand a min-heap, a max-heap is one comparator flip away. The rest of this article uses a min-heap, where the smallest element is always at index 0.

How insert and extract work

The heap property can break in exactly two ways. A new element is too small for its position and needs to move up. Or a replacement element is too large for its position and needs to move down. Sift-up fixes the first case. Sift-down fixes the second.

Sift-up (insert)

When you insert a value, place it at the end of the array. Compare it with its parent at position (i - 1) / 2. If it's smaller, swap them. Repeat from the new position until the value is larger than its parent or reaches the root.

Walk through inserting 3 into a min-heap array of [5, 8, 10, 12, 15].

The new element goes to index 5. Its parent is at index 2, which holds 10. Since 3 is smaller than 10, swap them. The array becomes [5, 8, 3, 12, 15, 10]. Now at index 2, the parent is at index 0, which holds 5. Since 3 is smaller than 5, swap again. The array becomes [3, 8, 5, 12, 15, 10]. Position is the root. Sift-up is complete.

The maximum number of swaps equals the height of the tree, which is O(log n).

Sift-down (extract-min)

Extracting the minimum means removing index 0. You can't just delete it and shift everything. Instead, move the last element to index 0, then sift it down. Compare it with both children, swap with the smaller child if it violates the heap property, and repeat until it's smaller than both children or reaches a leaf.

Take the heap [3, 8, 5, 12, 15, 10]. Remove 3 and move the last element 10 to index 0, giving [10, 8, 5, 12, 15]. The left child at index 1 is 8 and the right child at index 2 is 5. The smaller child is 5. Since 10 is greater than 5, swap them. The array becomes [5, 8, 10, 12, 15]. At index 2, the left child at index 5 doesn't exist because it's beyond the array length. No more children to compare, so sift-down is complete.

Both operations run in O(log n). Peeking at the minimum is O(1) because it's always at index 0. Fast insert, fast extract, instant access to the extreme value. That's why heaps are the go-to for priority-based problems.

Building a heap in O(n)

If you need a heap from an existing array, the naive approach is to insert elements one by one. Each insertion is O(log n), and you do it n times, giving O(n log n). That works but wastes effort.

Heapify does it in O(n) by working backwards. Start from the last non-leaf node at index n/2 - 1 and sift-down each node. Leaves are already valid heaps of size 1, so you skip them entirely. Each sift-down fixes the subtree rooted at that node.

The O(n) complexity is the part most explanations either skip or hand-wave. The reason comes down to where the work concentrates. Most nodes are near the bottom of the tree, and nodes near the bottom have very short sift-down distances. Half the nodes are leaves that require zero work. A quarter are one level up and need at most 1 swap. An eighth are two levels up and need at most 2 swaps. The total work sums to roughly 2n, not n log n. The formal proof uses a convergent geometric series, but the real insight is that the distribution of work is bottom-heavy, not uniform. Most textbooks just state the result. The actual reasoning behind it is worth understanding, because it shows up again in amortized analysis elsewhere.

This matters in interviews because building a heap from an unsorted array is a common sub-step in problems like "find the K largest elements" or "sort a nearly sorted array." If you claim the construction is O(n log n), you've missed an optimization the interviewer may specifically be testing.

Heap priority queue interview patterns

Heaps appear in interviews through two patterns almost every time. Top-K elements and the median finder both rely on the same thing: constant-time access to the extreme value in a collection that keeps changing.

Top-K elements

Maintain a min-heap of size k. Walk through the array. If the heap has fewer than k elements, insert. Otherwise, compare the current element with the heap's minimum at index 0. If the current element is larger, extract the minimum and insert the current element. After processing the entire array, the heap's minimum is the Kth largest.

Why a min-heap for the largest elements? You're using the heap as a bouncer. The smallest element in the heap is the threshold for entry. Anything below it gets rejected. After all elements pass through, the k survivors are the k largest, and the bouncer at index 0 is the Kth largest.

When k is much smaller than n, this significantly outperforms sorting. For "find the 10 largest elements in a million-element array," you're maintaining a 10-element heap instead of sorting a million elements.

Median finder

 This is a classic hard problem that shows up at Amazon, Apple, Google, and Microsoft.

Two heaps solve it. A max-heap holds the smaller half of all numbers. A min-heap holds the larger half. At any point, the max-heap's root is the largest of the small numbers, and the min-heap's root is the smallest of the large numbers. For an odd total count, the median sits at the max-heap's root. For an even count, it's the average of both roots.

On each insertion, add the number to the appropriate heap based on comparison with the current max-heap root. Then rebalance so neither heap has more than one extra element. Move a root from the larger heap to the smaller if they drift apart.

Finding the median is always O(1) because you're just reading roots. Insertion is O(log n) because each heap operation is logarithmic. Two heaps, constant-time median. That's the whole design.

This problem tests whether you can compose two heaps into a system where each heap has a clear job. If you understand sift-up and sift-down, the mechanics are obvious. Without that, the two-heap approach feels like a memorised trick you can't rederive under pressure.

Where the heap shows up next

The heap shows up as a building block in several advanced algorithms. Dijkstra's shortest path uses a min-heap as its frontier, extracting the closest unvisited node on each step. Heapsort builds a max-heap and repeatedly extracts the maximum to produce a sorted array. If sift-down is already second nature, both of these click quickly.

Heap problems have a recognisable shape. The problem involves repeated access to a minimum or maximum in a changing collection, or it asks for the "K smallest/largest" of something. If you spot those cues and immediately think "heap," you're reading the problem correctly. Codeintuition's Heap course covers 16 lessons across both the Top K Elements and Comparator patterns, including three design problems where you build a max-heap, a min-heap, and the median finder from scratch.

Start with the understanding lesson on heap fundamentals to see sift-up and sift-down traced frame by frame with illustrations before attempting any problems. The learning path places the Heap course after BST, so the transition from tree-based thinking to array-based storage makes sense by the time you arrive.

Before going all in, the free Arrays and Singly Linked List courses cover 15 patterns across two complete data structures with no time limit. The full learning path is $79.99/year, but those two courses are a good test of whether the construction-first teaching model clicks for you.

A year from now, you'll open a problem that mentions "K closest points" or "running median." Instead of guessing, you'll picture the array, trace the sift-down in your head, and know exactly which heap configuration to reach for. That confidence doesn't come from reading about heaps. You get it from building one yourself, tracing the swaps, and watching the invariant hold.