You extract the minimum from a min-heap of 10 elements. What happens next in the heap's internal array representation?
AThe second-smallest element, which is always one of the root's children, automatically becomes the new root
BThe array is scanned linearly to find the next minimum, which is moved to index 0
CThe last element in the array is moved to the root position and sifted down by swapping with the smaller child until the heap property is restored
DThe left subtree of the root becomes the new heap, discarding the right subtree
After extracting the root, the heap's structural integrity must be preserved: it must remain a complete binary tree. The cleanest way to do this is to move the last element in the array (the rightmost node at the deepest level) to the root position, then sift it down — repeatedly swapping it with the smaller of its children until the heap property is restored. This takes O(log n) time. Option A is the most common misconception: the second-smallest element is NOT guaranteed to be a child of the root in a heap (siblings have no ordering relationship to each other). Option B would take O(n) time and destroy the heap structure.
Question 2 Multiple Choice
In a 0-indexed min-heap stored as an array, the node at index 7 has its parent at index:
A3
B6
C4
D13
For a 0-indexed heap, the parent of node at index i is at index ⌊(i − 1) / 2⌋. For i = 7: ⌊(7 − 1) / 2⌋ = ⌊6 / 2⌋ = ⌊3⌋ = 3. The children of the node at index 3 are at indices 2×3+1 = 7 and 2×3+2 = 8, which confirms index 3 is the parent of index 7. Option B (6) would be the result of ⌊i/2⌋ (the 1-indexed formula applied incorrectly). Option C (4) is a common off-by-one error. Index arithmetic is the foundation of the array-based heap representation — getting it wrong produces silent, hard-to-debug errors.
Question 3 True / False
After inserting elements into a min-heap, the array representation contains the elements in sorted order from smallest to largest.
TTrue
FFalse
Answer: False
A heap is NOT sorted. The heap property only guarantees that every parent is smaller than or equal to its children — it says nothing about the relative ordering of sibling nodes or nodes at the same level. The smallest element is at the root (index 0), but the second-smallest could be anywhere among the root's children, and the third-smallest could be scattered further down. If you want elements in sorted order, you must perform heapsort: extract the minimum n times, each extraction costing O(log n), for a total of O(n log n). The misconception that heaps are sorted arrays is extremely common and leads to bugs when assuming random access to the k-th smallest element is O(1).
Question 4 True / False
A priority queue implemented as a min-heap supports O(1) access to the minimum element and O(log n) insertion and extraction.
TTrue
FFalse
Answer: True
Peeking at the minimum is O(1) because the minimum is always at the root (index 0 in a 0-indexed array) — no traversal needed. Insertion is O(log n): place the new element at the end of the array, then sift up along at most one root-to-leaf path of length O(log n). Extraction of the minimum is O(log n): move the last element to the root, then sift down along a similar path. This combination — constant-time peek, log-time insert and extract — is why heaps are the standard implementation for priority queues, outperforming sorted arrays (O(n) insertion) and unsorted arrays (O(n) extraction) for the typical priority queue workload.
Question 5 Short Answer
Why does a heap not guarantee that all elements are in sorted order, and how does this 'weak' ordering property actually make it more efficient for its intended use?
Think about your answer, then reveal below.
Model answer: A heap only guarantees the heap property: every parent is ≤ (min-heap) or ≥ (max-heap) its children. This says nothing about sibling ordering or any comparison between nodes not on the same root-to-leaf path. Full sorted order would require a much stronger invariant — maintained by BSTs or sorted arrays. The weak ordering is more efficient because maintaining it requires only O(log n) work per insertion or extraction: the sift-up or sift-down operation only traverses one path from root to leaf. Maintaining full sorted order on every insertion costs O(n) in an array or O(log n) in a balanced BST, but the BST has higher constant factors and worse cache behavior. For workloads that only need the current minimum or maximum — schedulers, Dijkstra's algorithm, simulation event queues — the heap's weak guarantee is sufficient and faster to maintain.
The heap's design is a lesson in matching data structure complexity to the actual access pattern. If you need arbitrary access (find the 5th smallest element), a heap is the wrong structure. If you only need the extreme element repeatedly, the heap's weak invariant provides exactly what you need at minimum overhead. This principle — sufficient invariants are better than unnecessarily strong ones — appears throughout algorithm design.