Practice question · Multiple choice
A binary heap lives in a flat array with no pointers at all, and children are found by arithmetic. Which property of the heap makes that possible?
Hints
- Ask what would break in the arithmetic if the tree had a hole in the middle.
- Two properties define a heap: shape and order. Which one does the array indexing rely on?
Show the answer
C. Completeness, so positions can be numbered without gaps
Why
Shape does the work, not order: no gaps means level-order numbering is dense, so children sit at 2i+1 and 2i+2 by arithmetic. A BST has no shape guarantee, so it needs pointers, and that is why a heap has the memory profile of an array while behaving like a tree.
Practise Heaps and Priority Management
The app has 6 more questions on this lesson, and keeps your place in the course. Computer Science I is free to start.