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
  1. Append the new item to the end of the array (keeping the complete shape).
  2. Compare with the parent; swap if it violates the property.
  3. Repeat upwards until the parent is smaller, or you reach the root.

12. Give pop in four steps.

Answer
  1. The extreme item is array[0].
  2. Replace array[0] with the last item and remove the last slot.
  3. Compare the new root with its children; swap with the smaller one.
  4. 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
OperationUnsorted listSorted listHeap
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

PassDateGot itCloseBlankQuestions missed
1
2
3

↑ Back to Data Structures — University-Style Teaching Notes