3.1Heap property and array layout
The idea
A binary heap is a complete binary tree stored in an array, where every parent is larger (max-heap) or smaller (min-heap) than its children.
Think of it like this: A company where every manager earns at least as much as each report, but two colleagues are not ranked against each other.
Why it exists
The array layout makes parent and child lookup free, so heaps are fast and compact.
How it works
- Children of i: 2i + 1 and 2i + 2. Parent: ⌊(i − 1)/2⌋.
- The tree is filled level by level, left to right.
- The root holds the extreme value.
- The leaves are the last ⌈n/2⌉ indices.
Worked example: Heap of size 10, index 4
Parent = 1, children would be 9 and 10 (only 9 exists). The leaves are indices 5 to 9.
Now play with it
- →Change n and i in the calculator.
- →Check that the first leaf index is ⌊n/2⌋.
In a max-heap the minimum is always one of the leaves (indices ⌊n/2⌋ … n − 1).
Check yourself
In a max-heap with n distinct elements, the smallest element is
Exam notes (the dense version)
A binary heap is a complete binary tree stored in an array: node i has children 2i + 1 and 2i + 2 (0-based) and parent ⌊(i − 1)/2⌋. In a max-heap every parent ≥ its children, so the maximum is at the root. There is no order between siblings. The leaves are the nodes with index ≥ ⌊n/2⌋. The height is ⌊log₂ n⌋.
Previous year questions: Heaps & Priority Queues (9)
PYQs are grouped by topic, so this is the full set for Heaps & Priority Queues; try the ones that match this subtopic. Open all 9 on the topic page.