Micro-questions over the heaps module. Answer in a full sentence before opening the toggle. Format explained in the arrays bank.
A. The one rule
1. What is a heap?
Answer
A tree-shaped structure with one rule — every parent is ordered relative to its children. That rule is weaker than full sorting, and the weakness is what makes it cheap to maintain.
2. State the heap property for a min-heap and a max-heap.
Answer
Min-heap: every parent both children. Max-heap: every parent both children.
3. What does the heap property deliberately not say?
Answer
Anything about siblings. Two children of the same parent are in no particular order relative to each other.
4. What sits at the root of a min-heap, and what does it cost to find?
Answer
The global minimum — and it costs nothing. You simply look at it.
5. Is a heap a sorted structure?
Answer
No. Printing a heap’s array gives something that looks almost random. It maintains one relationship — parent versus child — and refuses to order siblings, because knowing the minimum never required that work.
B. The array representation
6. What shape must a heap be, and why is that not decoration?
Answer
A complete binary tree — every level full except possibly the last, which fills from the left. That shape is what lets the whole tree live in a plain array with no pointers at all.
7. Give the three index formulas.
Answer
8. What does the array layout save?
Answer
Two pointers per node of memory, plus the cache misses — the whole structure is one contiguous block.
C. The operations
9. What is sift-up, and what does it cost?
Answer
Also bubble-up — after adding an item at the bottom, compare with the parent and swap upwards until the property holds. , because the tree’s height is .
10. What is sift-down?
Answer
Also bubble-down — after removing the root, move the last item to the top and swap downwards with the smaller child until the property holds. Also .
11. Give push in three steps.
Answer
- Append the new item to the end of the array (keeping the complete shape).
- Compare with the parent; swap if it violates the property.
- Repeat upwards until the parent is smaller, or you reach the root.
12. Give pop in four steps.
Answer
- The extreme item is
array[0]. - Replace
array[0]with the last item and remove the last slot. - Compare the new root with its children; swap with the smaller one.
- Repeat downwards until both children are larger, or you hit a leaf.
13. Why does pop move the last item to the root rather than promoting a child?
Answer
Because the tree must stay complete. Removing the last slot is the only removal that preserves the shape, so the array arithmetic keeps working.
14. In a min-heap sift-down, why swap with the smaller child?
Answer
Because the promoted child becomes the parent of the other one, and it must be both. Swapping with the larger child would immediately violate the property on the other side.
D. Heapify
15. What is heapify?
Answer
Turning an unordered array into a valid heap.
16. What does it cost naively, and what does it cost properly?
Answer
Naively — inserting one at a time — . Properly — sifting down from the middle of the array backwards — .
17. Give the counting argument for why it is .
Answer
About elements are leaves and need 0 swaps. are one level up and need at most 1. need at most 2, and so on:
Most nodes are near the bottom, where the work is cheapest.
18. Why does the naive version fail to get this saving?
Answer
Inserting sifts up, and most nodes are near the bottom — which is far from the root. Sifting down puts the cheap direction where the many nodes are.
19. Where do you start the bottom-up loop, and why?
Answer
At index — the last non-leaf node. Everything after it is a leaf and already a valid heap of one.
E. The priority queue ADT
20. What is the difference between a priority queue and a heap?
Answer
A priority queue is the ADT — add freely, always remove the highest priority. A heap is the usual implementation of it. This is the clearest example in the folder of why ADTs and implementations are different things.
21. List the priority queue ADT with heap costs.
Answer
insert ; peek_min ; extract_min ; is_empty/size ; heapify(list) ; decrease_key .
22. What is the catch with decrease_key?
Answer
It needs a way to find the item first, which a plain heap does not provide. This is why Dijkstra usually pushes a duplicate entry and skips stale ones instead.
23. Compare unsorted list, sorted list and heap on the three operations.
Answer
| Operation | Unsorted list | Sorted list | Heap |
|---|---|---|---|
insert | |||
peek_min | |||
extract_min |
24. State the heap’s whole value in one sentence.
Answer
It is good at all three at once, by maintaining exactly enough order to know the minimum and no more.
F. Python’s heapq
25. Is Python’s heapq a min-heap or a max-heap?
Answer
Strictly a min-heap.
26. What is the max-heap trick?
Answer
Negate on the way in and on the way out: push -value, and read -heappop(h).
27. How do you peek in heapq?
Answer
heap[0] — there is no peek function; the root is just index 0.
28. What does heapq.heapify(numbers) do, and at what cost?
Answer
Transforms the list in place into a valid heap, in .
G. Costs and traps
29. Give the full cost table.
Answer
Peek ; push ; pop ; build via heapify ; search for an arbitrary element ; space .
30. Why can you not use a heap to answer “does 42 exist?”
Answer
Heaps are not search trees. There is no ordering between siblings, so there is no branch to discard — you must scan every element. Use a hash map or a BST.
31. What is the tuple comparison crash, and what is the fix?
Answer
Storing (priority, item) raises TypeError when two priorities tie and item is unorderable. Fix: an incrementing counter tiebreaker — (priority, counter, item).
32. Building a heap from an existing array — what is the mistake?
Answer
Pushing one element at a time, at , when heapify does it in .
33. Summarise the heap in one sentence.
Answer
A complete tree in a flat array that maintains only the parent–child ordering — just enough to know the extreme in and change it in , and deliberately not enough to search.
Scorecard
| Pass | Date | Got it | Close | Blank | Questions missed |
|---|---|---|---|---|---|
| 1 | |||||
| 2 | |||||
| 3 |
Related
- Heaps & Priority Queues — the module
- Binary Trees — Question Bank — where the complete-tree array layout is derived
- Dijkstra — Question Bank — the heap’s most important customer
- Top K Elements — the pattern built on it
Software engineering
Infrastructure & security
Computer science
Hardware & engineering