Question 1

What is a heap and how does it differ from a BST?

Accepted Answer

Give the definition precisely: "A heap is a complete binary tree maintaining one invariant — in a min-heap every parent is less than or equal to its children. The smallest element is always at the root." Then draw the difference from its most important point: "In a BST there is order between left and right, which is why search is O(log n). In a heap there is no order between siblings — only the parent–child relation is constrained. So searching for an arbitrary value in a heap is O(n): you have no way to know which branch to take." Summarise in one line — this is the formulation interviewers like: "A BST is an order structure, a heap is a priority structure. A heap answers one question fast: which is the smallest (or largest)?" Then add the implementation detail: "Because it is a complete tree, a heap lives in an array — left = 2i+1, right = 2i+2, parent = (i−1)/2. No pointers, excellent cache locality." Close with complexities: peek O(1), insert and extract O(log n), build-heap O(n), search O(n).

Question 2

How would you find the 10 largest numbers out of a million?

Accepted Answer

Name the naive solution first so the comparison is visible: "You could sort everything and take the first 10 — O(n log n) time and holding all the data in memory." Then give the real solution: "I keep a min-heap of size k = 10. For each new element: if the heap holds fewer than 10, push it. If it is full, I look at the root — the smallest element I am keeping — in O(1); if the new element is larger I pop the root and push it, otherwise I do nothing." Always explain why a min-heap — this is the question's real checkpoint: "I am keeping the 10 largest, so at each step the candidate I must discard is the SMALLEST of the ones I hold. A min-heap shows it at the root in O(1). A max-heap would be wrong: its root is the largest, but I need the one to evict." State complexity on both axes: "O(n log k) time — with k = 10 that is very close to O(n) in practice. Memory is O(k), just 10 elements." The final and strongest point: "The memory advantage is decisive here — this approach works on a stream. If the million numbers arrive from a file or the network, you never hold them all; the sorting approach is forced to." Know the alternative too: quickselect gives O(n) on average, but requires all the data in memory and has an O(n²) worst case.

Question 3

Why is build-heap O(n) rather than O(n log n)?

Accepted Answer

Name the naive reasoning first and show exactly where it fails — that is where this answer gets its strength: "At first glance it looks like this: n elements, each sifting O(log n), therefore O(n log n). That reasoning assumes every node travels the FULL height of the tree — which is not true." Then give the correct count: "I heapify bottom-up. Half the nodes are leaves and never move — 0 steps. A quarter move at most 1 step, an eighth 2 steps, and so on. The sum is the series n/2·0 + n/4·1 + n/8·2 + ..., which converges to 2n — so O(n)." Give the intuition in one sentence, because that is what the interviewer is listening for: "The vast majority of nodes sit at the bottom where there is little work to do; the nodes that do a lot of work are few." Always add the practical consequence: "So to turn an existing array into a heap, use bottom-up build-heap rather than calling insert n times (which really is O(n log n)). This also explains why heapsort is O(n log n): building is O(n), but the n subsequent extracts are O(n log n) — the second part dominates."

Question 4

Where have you used, or would you use, a priority queue in a real project?

Accepted Answer

This question checks whether you can connect theory to practice, so give concrete scenarios: Task/job scheduler: jobs arrive with priorities and deadlines; the heap always keeps the most urgent at the root. poll() is O(log n), so picking the next one stays cheap even with thousands queued. Rate limiting / retry queue: failed requests are held in a heap keyed by their retry time; the earliest is always at the root. Top-N analytics: the 10 endpoints with the most errors from a log stream. A min-heap of size k gives O(n log k) time and O(k) memory — without loading the whole log. Merging k sorted sources: turning results from several sorted files or shards into one sorted stream — O(N log k). Dijkstra / A*: shortest paths in a graph; each step needs the closest unprocessed node — that is a priority queue directly. Then add the language detail, since it signals practical experience: "Kotlin/Java ship java.util.PriorityQueue; Dart has HeapPriorityQueue in package:collection; JS has no built-in heap — I either write one or take a library." Mention one trap too: "Iterating a PriorityQueue does NOT give sorted output — the underlying array is in heap layout. Sorted results require repeated poll(). This is a mistake people hit often in real code."

Question 5

How do you choose between a heap and a sorted array?

Accepted Answer

Reduce the choice to two questions: how often the data changes and which question you are asking. "A sorted array is excellent for static data: binary search in O(log n), O(1) random access, free sorted iteration, perfect cache locality. But inserting an element is O(n), because everything after it must shift." "A heap is the reverse: insert and extract are O(log n), but you only see ONE element cheaply — the minimum or maximum. Arbitrary search is O(n) and sorted iteration is O(n log n)." The rule: "If the data changes frequently and I always need 'the next most important element' — a heap. If the data rarely changes and I need search, ranges or sorted iteration — a sorted array." Ground it with an example: "A live task queue — heap, because new tasks arrive constantly and I only need the most urgent. A price table refreshed once a day — sorted array, because reads dominate and writes are almost nonexistent." Mentioning the third option completes the answer: "If I need both order and frequent mutation, the third choice is a balanced tree — TreeMap/SplayTreeMap: insert, delete, search and range queries all O(log n)."

Operation	Complexity	Why
peek (min/max)	O(1)	Always at `array[0]`
insert	O(log n)	Append + sift up, at most the height
extractMin / extractMax	O(log n)	Take the root, move the last up, sift down
build-heap (from n elements)	O(n) — not O(n log n)	Most nodes sit low and move little; the sum collapses to O(n)
search (arbitrary value)	O(n)	No order between siblings — you cannot pick a branch
sorted iteration	O(n log n)	You must extract repeatedly (heapsort)

Heap and Priority Queue

📚 Sources and documentation