Heaps / Priority Queues
A tree-shaped structure that keeps the min (or max) element accessible in O(1), with O(log n) insert and remove.
Try answering in your head first, then click a question to check the model answer.
Q1.Explain why a heap gives O(1) access to the min/max but O(log n) for insert and remove.(show answer)
The heap property guarantees the min (or max) is always at the root, so reading it is O(1). But inserting or removing must restore the heap property afterward — a new element is added at the bottom and "bubbled up" (swapped with its parent) until it's in the correct position, or the root is removed and the last element is moved to the root and "bubbled down" — both operations take time proportional to the tree's height, which is O(log n) for a heap with n elements.
Q2.How would you efficiently find the k largest elements in a large array using a heap?(show answer)
Maintain a min-heap of size k. Process each element: if the heap has fewer than k elements, add it; otherwise, compare it to the heap's minimum (the root) — if the new element is larger, remove the root and insert the new element instead. After processing all n elements, the heap holds the k largest. This runs in O(n log k), better than sorting the whole array (O(n log n)) when k is much smaller than n.
Q3.Why is a heap typically implemented as a flat array rather than with explicit node/pointer objects like a general tree?(show answer)
A complete binary tree (which a heap always is) has a predictable structure: for a node at array index i, its children are at 2i+1 and 2i+2, and its parent is at (i-1)/2 — no pointers needed at all. This array representation avoids per-node pointer memory overhead and gives better cache locality than a pointer-based tree, since related elements are stored contiguously.
Q4.What's the time complexity of building a heap from an unsorted array of n elements, and why is it better than n individual insertions?(show answer)
Building a heap from an existing array ("heapify") runs in O(n) total, not O(n log n) as n individual insertions would suggest. This is because heapify works bottom-up: most nodes are near the bottom of the tree and need very little "bubble down" work, and only a few nodes near the root need close to the full O(log n) — the sum across all nodes works out to O(n) rather than O(n log n).