DSA · Heaps & priority queues

The tree that lives in an array

Q: Why can a binary tree be stored in a flat array, and where do 2i+1 and 2i+2 come from?

Because the tree is complete there are no gaps, so numbering the nodes level by level from 0 maps them one-to-one onto array indices. Node i is followed by the next two unclaimed slots, which work out to 2i+1 and 2i+2 , and running it backwards gives the parent as (i-1)/2 with integer division. No pointers, and the array is contiguous, so it is cache-friendly too.

Q: Can you search a heap in O(log n)?

No — searching is O(n) . The heap property only relates a parent to its children, so at any node both subtrees may contain the value and you cannot rule either out. A BST can, which is the difference between the two. If you need lookups, keep a hash map from value to array index alongside the heap; that is exactly how Dijkstra’s decrease-key is implemented.

Q: How would you find the k-th largest element of an array?

Keep a min -heap of size k. Push each element and pop the root whenever the size passes k, so the heap always holds the k largest values seen. Its root is the weakest of those, which is the k-th largest. O(n log k) time and O(k) space, and unlike quickselect it works on a stream you can only read once.

A heap keeps the largest value at index 0 and never sorts anything else. Insert, remove, and the index arithmetic that makes both cost log n.

Sift a value up and down a live heap →

One array, two pictures. arr = 9 8 5 3 4 · left child of i is 2i+1 · right child is 2i+2 · parent is (i-1)/2

01 The idea

A heap is lazy on purpose

A priority queue has one job: whatever arrives, hand back the most important item next. You could keep a sorted array — then reading the maximum is instant, but every insert shifts elements along, which is O(n). You could keep an unsorted list — then insert is instant, but finding the maximum scans everything, which is O(n) again. Each choice makes one operation free by making the other one slow.

A heap refuses both extremes by keeping the array almost sorted. Every parent must beat both of its children, and nothing else is promised. Siblings are never compared. A value two levels down in one branch can be larger than a value one level down in the other. That rule is strong enough to pin the maximum at index 0, and weak enough that repairing it after a change only touches one path from top to bottom — about log n cells out of n.

A heap keeps exactly one promise: the winner sits at index 0. It never sorts the rest, and that laziness is why insert and remove cost log n instead of n.

Complete binary treeEvery level is full except possibly the last, and the last fills left to right. There are no gaps, so the tree needs no pointers: number the nodes level by level from 0 and node i has children 2i+1 and 2i+2.

Heap propertyEvery parent is at least as large as both of its children (a max-heap), or at most as small as both (a min-heap). It says nothing about siblings, so a heap is not a sorted array.

Priority queueThe job, not the structure: insert anything, always remove the most urgent item. A heap is how you do that job in O(log n), which is why the two words get used as if they meant the same thing.

02 Hand trace

Five inserts into an empty max-heap

The values are 3 8 5 9 4 and they arrive one at a time. This is the heap the whole lesson uses. Each new value goes into the next free array slot — the only slot that keeps the tree complete — and then climbs while it beats its parent. Climbing one level is called a sift up, and in the array it is nothing more than swapping cell i with cell (i-1)/2.

        9              <- index 0, always the maximum      /   \     8     5           <- indices 1 and 2    / \   3   4               <- indices 3 and 4    arr    9  8  5  3  4   index  0  1  2  3  4

Now watch it being built. Each row is one operation: an insert, or one swap of the sift up. Rose is the value that just moved, a dot is a slot the heap has not reached yet.

insert 33····the heap was empty, so 3 is the root at index 0

insert 838···parent of index 1 is index (1-1)/2 = 0, holding 3 — 8 is bigger

swap 1,083···8 climbs one level and is now the root

insert 5835··parent of index 2 is index 0, holding 8 — 5 loses, so it stays

insert 98359·parent of index 3 is index 1, holding 3 — 9 is bigger

swap 3,18953·now compare with index 0, holding 8 — 9 is bigger again

swap 1,09853·two climbs took 9 from the bottom row to the root

insert 498534parent of index 4 is index 1, holding 8 — 4 stays put

result98534valid max-heap · 5 comparisons, 3 swaps

Two things to take from this. First, the array is not sorted — 9 8 5 3 4 has 3 sitting before 4 — and it never needs to be. Second, every tree move is an array move: when 9 climbed from index 3 to index 1, two cells traded places, and the index went from i to (i-1)/2. Those are the same event described twice. Section 03 is that climb written as a loop.

03 The code

Two repairs: one walks up, one walks down

A heap only ever breaks in one place at a time, and there are only two ways to break it. Add a value at the bottom and it may be too big for its parent, so you repair upwards. Remove the root and the hole at the top must be filled by the last element, which is probably too small for its children, so you repair downwards. Every other heap operation is one of these two functions with a wrapper.

Insert · sift up

function insert(heap, v):  append v at the end          # keeps the tree complete  i = size(heap) - 1  while i > 0:    p = (i - 1) / 2              # the parent    if heap[i] <= heap[p]: break    swap heap[i], heap[p]    i = p

Extract max · sift down

function extractMax(heap):  top = heap[0]                 # the answer  move the last element to index 0, shrink by 1  i = 0  while 2*i+1 < size(heap):      # a left child exists    big = 2*i+1                 # start with the left    if 2*i+2 < size(heap) and heap[2*i+2] > heap[big]:      big = 2*i+2               # the right one is bigger    if heap[big] <= heap[i]: break    swap heap[i], heap[big]    i = big  return top

Why up needs one comparison per level and down needs two. A node has exactly one parent, so sifting up has nothing to choose: compare, swap or stop. A node has two children, so sifting down must first decide which child it is even arguing with — that is line 7 — and only then compare. Same number of levels, twice the comparisons.

Why you must take the bigger child. When 4 sat at the root above children 8 and 5, swapping it with 5 would have put 5 above 8 — broken again, immediately. Only the larger of the two children is guaranteed to be a legal parent for both of them.

Why the last element fills the hole, and not the second largest. The second largest is easy to find — it is heap[1] or heap[2] — but promoting it just moves the hole down a level, and now the tree has a gap in the middle and is no longer complete. Moving the last element up fixes the shape in one move and leaves exactly one broken parent-child relationship to repair.

Why both loops run at most log n times. Each iteration moves i exactly one level: i → (i-1)/2 halves it, i → 2i+1 doubles it. A complete tree of n nodes has floor(log2 n) + 1 levels — our 5-node heap has 3 — so neither loop can iterate more than log2 n times. That is the entire complexity argument, and it is why a heap beats both the sorted array and the unsorted list.

A min-heap is the same code. Flip the two comparisons on lines 6 and 9 and swap "bigger" for "smaller" on line 7. The shape, the index arithmetic and every complexity are identical. Keep this in your pocket — the standard trick for "k-th largest" uses a min-heap.

Everything else is a wrapper around those two

Operation	How it is built	Cost
Peek at the maximum	Read heap[0]. There is nothing to search.	`O(1)`
Insert	One sift up from the last slot.	`O(log n)`
Extract the maximum	One sift down from the root.	`O(log n)`
Replace the maximum	Overwrite heap[0], then one sift down. Cheaper than a pop followed by a push.	`O(log n)`
Build a heap from a raw array	Sift down at every index from n/2 - 1 back to 0. Indices n/2 onwards are leaves, and a leaf is already a valid heap of one.	`O(n)`
Heap sort	Build the heap, then n times: swap the root into the slot the heap is giving up and sift down.	`O(n log n)`

Build is O(n), and that surprises people. The nodes that could travel furthest are the fewest. Half the nodes are leaves and sift down does nothing to them. The n/4 nodes one level up sink at most 1 level, the n/8 above them at most 2, and so on — so the total work is n(1/4 + 2/8 + 3/16 + …), a series that converges to n. Inserting one at a time is the mirror image and that is exactly why it is worse: it starts every single element at the bottom, where the path to the root is longest.

Heap sort on the same five values

Once you have a max-heap, sorting is free of new ideas. The largest value is at index 0 and its final home is the last slot, so swap those two, shrink the heap by one, and sift the newcomer down. The green cells are finished and are no longer part of the heap.

start98534a valid max-heap of 5 nodes

park 984539swap index 0 with index 4, shrink to 4, sift 4 down one level

park 854389swap index 0 with index 3, shrink to 3, sift 3 down

park 543589swap index 0 with index 2, shrink to 2, sift 3 down

park 434589swap index 0 with index 1, shrink to 1 — a one-node heap has nothing to sift

result34589sorted ascending, in the same array, no extra memory

Why the sorted array comes out ascending from a max-heap. You are filling the array from the right with the largest remaining value each time. Use a min-heap instead and the same code sorts descending — which is the answer to a common follow-up.

05 Cheat sheet

The numbers you will be asked for

Operation	Cost	Why
Read the maximum	`O(1)`	It is arr[0]. The heap property guarantees it and there is nothing to search.
Insert	`O(log n)`	Sift up climbs one level per swap, and a complete tree of n nodes has floor(log2 n) + 1 levels.
Extract the maximum	`O(log n)`	Sift down can fall from the root all the way to a leaf, two comparisons per level.
Build a heap from an array	`O(n)`	Bottom-up sift down from n/2 - 1 to 0. Half the nodes are leaves and never move.
Build a heap by n inserts	`O(n log n)`	Every element starts in the bottom row, where the path to the root is longest.
Find an arbitrary value	`O(n)`	Siblings are unordered, so no comparison tells you which subtree to enter. You scan.
Delete an arbitrary value	`O(n)`	Finding it is the expensive part. Once you know its index, the repair is one sift, so O(log n).
Heap sort — best, average, worst	`O(n log n)`	Build in O(n), then n extractions at O(log n). The work is set by the height of the tree, not by the data, so no input drops it below n log n — not even an already sorted one.
Extra space	`O(1)`	The tree is the array. Write both sifts as loops and there is no recursion stack either.

Build in O(n), not O(n log n)They are two different procedures. Bottom-up sift down is O(n) because n(1/4 + 2/8 + 3/16 + …) converges to n. Repeated insertion is O(n log n) in the worst case. If the interviewer says "O(n)", they mean the first one.

In-place but not stableHeap sort uses O(1) extra space and O(n log n) time on every input, including one already sorted. Equal keys get reordered, because a single swap can throw a value right across the array. Real libraries keep it as introsort's fallback for when quicksort degrades.

One question onlyA heap answers "what is the most extreme item?" The second largest is cheap too — it has to be arr[1] or arr[2]. Ask anything past that, like "is 4 in here?", and the guarantee runs out and you are scanning n cells.

06 Where & why

A heap is for one end of the data, while it is still arriving

A heap is not a sorted container and it is a poor lookup table. Its value is narrow and real: it hands you the extreme item cheaply, over and over, while new items keep being added. Almost every heap question in an interview is one of the four shapes below.

Reach for it when…

You need the k-th largest, in one passKeep a min-heap capped at k. Push everything; whenever the size passes k, pop the root. The root is then the answer. O(n log k) time, O(k) space, and it works on a stream you can only read once.

You need the top K frequent itemsCount with a hash map first, then run that same size-k min-heap over the m distinct keys, comparing on count. O(n + m log k), instead of sorting all m counts.

You need the median of a streamTwo heaps facing each other: a max-heap for the smaller half, a min-heap for the larger half, sizes never differing by more than one. Insert is O(log n) and reading the median is O(1).

You need "the next thing to happen"OS schedulers, event-driven simulations, Dijkstra and A*, Huffman coding and k-way merges all repeat one question — which pending item is most urgent? — while new items keep arriving. That is the definition of a priority queue.

Use something else when…

Situation	Better choice	Why
You need every element in sorted order	The library sort — Timsort, introsort	A heap gives you one element at a time at O(log n) each. A comparison sort does the whole job in one O(n log n) pass with far better constants and cache behaviour, and Timsort is stable.
You need to find, update or delete an arbitrary value	A balanced BST (TreeMap), or a hash map beside the heap	Searching a heap is O(n) because siblings are unordered. Dijkstra's decrease-key is done exactly this way: a map from each value to its current index, so the sift can start in O(1).
You need the smallest and the largest cheaply	An ordered set — TreeSet, std::set	One heap pins one end only. An ordered set gives you both ends, plus ordered iteration, for the same O(log n) per operation.
You need the k-th largest once, in memory, with k large	Quickselect	Average O(n) against the heap's O(n log k). The catch: it reorders your array, its worst case is O(n²) without a good pivot rule, and it cannot run on a stream.

Interviewers rarely ask you to implement a heap. They ask a question containing the words top, k-th, closest, most frequent, or as they arrive — and every one of those is a heap, usually a min-heap of size k.

07 Interview questions

What actually gets asked

Read the question, answer it out loud, then open the card. Each answer is about twenty seconds spoken.

What is a heap?

A complete binary tree in which every parent beats both of its children, stored in a plain array with no pointers. That gives O(1) access to the extreme value and O(log n) insert and remove. It is not sorted — only the root is guaranteed, which is why our example heap is 9 8 5 3 4 and not 9 8 5 4 3.

What is the difference between a heap and a priority queue?

A priority queue is the interface: insert, and remove the most urgent item. A heap is the usual implementation. You could implement the same interface with a sorted array or an unsorted list, but those make one operation O(1) and the other O(n). The heap is chosen because it puts both at O(log n).

Why can a binary tree be stored in a flat array, and where do 2i+1 and 2i+2 come from?

Because the tree is complete there are no gaps, so numbering the nodes level by level from 0 maps them one-to-one onto array indices. Node i is followed by the next two unclaimed slots, which work out to 2i+1 and 2i+2, and running it backwards gives the parent as (i-1)/2 with integer division. No pointers, and the array is contiguous, so it is cache-friendly too.

Why is insert O(log n)?

The new value goes into the last slot and then swaps with its parent while it is bigger. Each swap climbs exactly one level, and a complete tree of n nodes has floor(log2 n) + 1 levels, so there can be at most log2 n swaps. The best case is one comparison and no swap — that is inserting 4 into 9 8 5 3 in our trace.

Why does extract-max need two comparisons per level when insert needs one?

A node has one parent but two children. Sifting up has nothing to choose: compare with the parent, swap or stop. Sifting down must first decide which child it is competing with — one comparison — and only then compare that child against the sinking value. Same number of levels, roughly twice the comparisons.

When you delete the root, why do you move the last element up instead of the bigger child?

To keep the tree complete. Promoting a child just moves the hole down a level and leaves a gap in the middle of the array, so the shape is broken and the index arithmetic stops working. Moving the last element to index 0 repairs the shape in one move, and leaves exactly one broken parent-child relationship, which one sift down fixes.

Is building a heap O(n) or O(n log n)?

Both, depending on how you build it. n successive inserts is O(n log n) in the worst case, because every element starts in the bottom row where the climb is longest. Bottom-up sift down from index n/2 - 1 to 0 is O(n): half the nodes are leaves that never move, a quarter sink at most one level, and the series n(1/4 + 2/8 + 3/16 + …) converges to n.

What is heap sort’s complexity, is it stable, and why does nobody use it?

O(n log n) in the best, average and worst case, with O(1) extra space — build the heap in O(n), then extract n times. It is not stable, because one swap can throw an element right across the array. It loses to quicksort in practice on cache behaviour, since sift down jumps between distant indices, so libraries keep it only as introsort’s fallback when quicksort degrades.

Can you search a heap in O(log n)?

No — searching is O(n). The heap property only relates a parent to its children, so at any node both subtrees may contain the value and you cannot rule either out. A BST can, which is the difference between the two. If you need lookups, keep a hash map from value to array index alongside the heap; that is exactly how Dijkstra’s decrease-key is implemented.

How would you find the k-th largest element of an array?

Keep a min-heap of size k. Push each element and pop the root whenever the size passes k, so the heap always holds the k largest values seen. Its root is the weakest of those, which is the k-th largest. O(n log k) time and O(k) space, and unlike quickselect it works on a stream you can only read once.

How do you find the median of a data stream?

Hard

Given an array and a window size k, return the maximum of every window of k consecutive elements.

Follow-up

A heap cannot delete the element that has just fallen out of the window — removing an arbitrary value is O(n), as the cheat sheet says. Get the heap version right first, then find the O(n) solution that keeps no heap at all, and say what the heap was buying you in the first place.

Show the hint

You never have to delete from the middle: leave stale entries sitting in the heap and throw one away only when it surfaces as the root. For that to be possible, each entry has to carry the index it came from.