A Heap is a specialized tree-based data structure that satisfies two fundamental invariant rules: the Shape Property and the Heap Property.
Heaps serve as the physical data structure behind the Priority Queue Abstract Data Type.
The Two Invariants of a Binary Heap
1. Shape Property (Complete Binary Tree)
A binary heap must be a Complete Binary Tree:
- Every level of the tree is completely filled, except possibly the last level.
- On the last level, all nodes must be packed as far to the left as possible with zero gaps.
Valid Complete Binary Tree:
[ 10 ]
/ \
[ 15 ] [ 20 ]
/ \
[ 40 ] [ 50 ]
INVALID (Gap on the left):
[ 10 ]
/ \
[ 15 ] [ 20 ]
\ /
[ 50 ] [ 40 ] <-- NOT a complete tree!
Why the complete tree rule matters: Because it is complete, a heap requires zero node objects or pointers. It can be mapped 100% losslessly into a compact, contiguous Array!
2. Heap Property (Ordering)
- Min-Heap Property: The key at any node is less than or equal to the keys of its children. The smallest element is always at the root.
- Max-Heap Property: The key at any node is greater than or equal to the keys of its children. The largest element is always at the root.
Min-Heap:
[ 4 ]
/ \
[ 10 ] [ 7 ]
/ \ /
[ 12 ] [15][ 9 ]
Core Operations and Complexity
| Operation | Description | Time Complexity |
|---|---|---|
peek() | Inspects root (min or max element) | O(1) |
insert(x) | Adds item at next leaf and sifts up | O(log n) |
extract() | Removes root, moves last leaf to root, sifts down | O(log n) |
buildHeap() | Builds heap from an unsorted array | O(n) (Linear time!) |
Summary
- A Binary Heap satisfies the Complete Binary Tree shape property and the Min/Max ordering property.
- The extreme element (minimum or maximum) is always accessible in
O(1)constant time. - Insertions and deletions take logarithmic
O(log n)time via sift-up and sift-down operations.