A heap stores an almost-complete binary tree in an array. This chapter develops
the heap property, insertion, root deletion, heapify, bottom-up heap construction,
heap sort, amortized analysis, and the Fibonacci heap.
9.1Why Heaps?
The benefit of a heap
A heap keeps the minimum or maximum element at its root, so finding that
extreme takes constant time while insertion and root deletion remain logarithmic.
Structure
Insert
Search
Find extreme
Delete extreme
Unsorted array
O(1)
O(n)
O(n)
O(n)
Sorted array
O(n)
O(log n)
O(1)
O(n)
Linked list
O(1)
O(n)
O(n)
O(n)
Min heap
O(log n)
O(n)
O(1) · find min
O(log n) · delete min
Max heap
O(log n)
O(n)
O(1) · find max
O(log n) · delete max
9.2Complete Binary Trees
Full binary tree
Every node has either zero or two children.
Complete binary tree
Every level is full except possibly the last, which fills from left to right.
Fill the tree level by level, from left to right
This is the structural rule used by a heap.
complete tree
Tree height
Height counts edges from the root to the deepest leaf.
h = ⌊log₂ n⌋
Maximum nodes
For a complete tree of height h:
n = 2h+1 − 1
Nodes of height h
In a complete tree:
⌈n / 2h+1⌉
For n = 15
Leaf indices run from ⌊15/2⌋ + 1 = 8 through 15.
Nodes of height 1: ⌈15/2²⌉ = 4.
9.3Array Representation of a Heap
The slides use 1-based indices
For a node at index i, its left child is
2i, its right child is
2i + 1, and its parent is
⌊i/2⌋.
Synchronised tree and array
Switch between the complete and incomplete examples from the slides.
Incomplete-tree example from the slides[25, 13, 22, 10, —, —, 13] has empty positions 5 and 6 before the value at position 7.
Array representation of the lecture max heap
The tree and its 1-based array store exactly the same heap: 16, 14, 10, 8, 7, 9, 3, 2, 4, 1.
1-based array
9.4The Heap Property
Definition · Heap
A heap is a tree-based data structure implemented as an almost-complete
binary tree: nodes fill level by level and from left to right.
Max heap
Every parent is greater than or equal to each child:
A[parent(i)] ≥ A[i].
Min heap
Every parent is less than or equal to each child:
A[parent(i)] ≤ A[i].
Every subtree is also a heap
The (sub)root nodes of the subtrees must also satisfy the heap property.
Leaf nodes satisfy it automatically
Leaf nodes inherently satisfy the heap property, as they have no children to compare with.
Subtree roots and leaf nodes in the lecture min heap
The exact example is 5, 7, 10, 11, 12, 13, 15.
min heap
Verify every parent–child relation
Each subtree root must satisfy the same heap property.
Immediate consequence
A descending array is always a max heap, and an ascending array is always a min heap.
Leaf nodes satisfy the property automatically because they have no children.
9.5Insertion into an Existing Max Heap
Insert 77 and adjust upward
Append at the next free position, then repeatedly compare with the parent.
send upward
Insertion complexity
Minimum comparisons: 1. Maximum comparisons: the tree height,
O(log n).
9.6Deletion from an Existing Max Heap
Heap deletion
Only the root is removed by the standard heap deletion operation.
Replace it with the last element, shrink the heap, and adjust downward.
Delete 77 and restore the max-heap property
At each step, compare the node with both children and swap with the larger child.
send downward
Deletion complexity
Adjustment moves toward the leaves and takes O(log n).
9.7Heapify Procedure
Heapify converts a subtree into a heap. When called on a node, it makes the
subtree rooted at that node satisfy the heap property.
def heapify(arr, n, i):
largest = i
left = 2 * i + 1
right = 2 * i + 2
if left < n and arr[left] > arr[largest]:
largest = left
if right < n and arr[right] > arr[largest]:
largest = right
if largest != i:
arr[i], arr[largest] = arr[largest], arr[i]
heapify(arr, n, largest)
Index convention
The diagram keeps the slides’ 1-based labels. The Python program uses 0-based indices,
so its children are 2i + 1 and 2i + 2.
MAX-HEAPIFY(A, 2)
Find the largest of the node and its children, swap, then continue in the affected subtree.
9.8Building a Heap
def build_max_heap(arr):
n = len(arr)
# Begin at the last non-leaf node
for i in range(n // 2 - 1, -1, -1):
heapify(arr, n, i)
Bottom-up order
Start at the last non-leaf node and move toward the root. Leaves already
satisfy the heap property.
Build a max heap from 4, 1, 3, 2, 16, 9, 10, 14, 8, 7
Every call works on a subtree whose children are already heaps.
Why bottom-up construction is O(n)
height 0
≈ n/2 nodes · cost 0
height 1
≈ n/4 nodes · cost 1
height 2
≈ n/8 nodes · cost 2
height 3
≈ n/16 nodes · cost 3
Σh=0⌊log n⌋ ⌈n / 2h+1⌉ · ch
≤ cn · Σh=0∞ h / 2h
= cn · 2
= O(n)
Why not start at the root?
Top-down repeated insertion can take O(n log n).
Bottom-up heapify uses O(n) time because most nodes are close to the leaves.
9.9Heap Sort
HEAPSORT(A):
BUILD_MAX_HEAP(A)
for end from len(A) - 1 down to 1:
swap A[0] and A[end]
heapify(A, end, 0)
Move each maximum into the sorted suffix
The active heap shrinks from the right after every extraction.
Combine the existing n keys and m new keys, then build once:
O(n + m).
Q2 · Seventh smallest in a min heap
Repeated delete-min takes O(7 log n), which is
O(log n).
Q3 · Smallest in a max heap
Inspect the leaves: O(n/2) =
O(n).
Q4 · Largest in a min heap
Inspect the leaves: O(n/2) =
O(n).
Q5 · Delete an arbitrary min-heap key
Search O(n), then adjust O(log n): total
O(n).
Q6–Q7 · Algorithms
Write Min-Heapify for 1…9, then use heap sort for descending order.
Q8 · Classify each array
Check every child against its parent.
Result: not checked
show Q6 and Q7 guidance
Q6: The ascending input 1, 2, 3, 4, 5, 6, 7, 8, 9 already satisfies the min-heap property, so Min-Heapify makes no swap.
Q7: To obtain descending order, build a min heap and repeatedly move the minimum to the end of the active heap.
9.11Amortized Time Complexity
Definition
Amortized analysis averages the cost of an operation over a sequence of operations. Expensive operations may be rare while cheap operations are frequent.
Problem
Some operations are expensive but rare, while others are cheap and frequent.
Solution
Amortized analysis averages the cost over a sequence of operations.
Example · finding the k-th smallest element in a given arrayCan we use linear search?
A linear scan takes O(n) for every selection. For all n selections that becomes O(n²), so sorting once gives the better total cost O(n log n).
Repeated k-th-smallest queries
Sort once, then answer each indexed selection in constant time.
Selections: —
one sort + n selections = O(n log n) + n·O(1)
(n log n + n) / n = log n + 1
amortized cost per selection = O(log n)
9.12Fibonacci Heap
Structure
A Fibonacci heap is a collection of trees that satisfy the min-heap property.
It supports efficient merging and decrease-key operations.
Amortized operation bounds:
InsertO(1)
Find-minO(1)
Delete-minO(log n)
Decrease-keyO(1)
MergeO(1)
These are amortized bounds over a sequence of operations;
an individual operation can occasionally cost more.