Heap Operations

All max-heap operations run in $O(\log n)$ time, where $n$ is the number of elements in the heap. Each operation works by traversing a single path from root to leaf (or leaf to root), bounded by the heap height $\lfloor \log_2 n \rfloor$.

Max-Heapify (Bubble-Down)

Purpose: Restore the max-heap property at node $i$, assuming the subtrees rooted at $i$‘s children are already valid max-heaps.

Algorithm:

1. Let $l = 2i$, $r = 2i + 1$.
2. Set largest to $i$ if $A[i] \ge A[l]$ (or $l$ exceeds heap size), else to $l$.
3. If $r$ is within heap and $A[r] > A[\text{largest}]$, set largest to $r$.
4. If largest $\ne i$, swap $A[i]$ and $A[\text{largest}]$, then recursively call Max-Heapify on largest.

Time: $O(\log n)$ — each swap moves down one level, at most the height of the heap.

Walkthrough

Starting with a heap violation at the root: $A = [4, 14, 10, 8, 7, 9, 3, 2, 1]$ (node $A[1] = 4$, children $14$ and $10$):

Step	Current node	Children	Largest	Action
1	$4$ at index 1	$14$, $10$	$14$ at index 2	Swap 4 and 14
2	$4$ at index 2	$8$, $7$	$8$ at index 4	Swap 4 and 8
3	$4$ at index 4	$2$, $1$	$4$ at index 4	No swap; done

Result: $[14, 8, 10, 4, 7, 9, 3, 2, 1]$ — a valid max-heap.

Insert (Bubble-Up)

Purpose: Insert a new key into the heap.

Algorithm:

1. Increment heap_size; place the new key at $A[\text{heap\_size}]$.
2. Set $j = \text{heap\_size}$.
3. While $j > 0$ and $A[j] > A[\text{parent}(j)]$:
4.  Swap $A[j]$ and $A[\text{parent}(j)]$.
5.  $j = \text{parent}(j)$.

Time: $O(\log n)$ — at most one swap per level up to the root.

Extract-Max

Purpose: Remove and return the largest element (the root).

Algorithm:

1. If the heap is empty, error.
2. Store $A[1]$ (the maximum).
3. Swap $A[1]$ with $A[\text{heap\_size}]$.
4. Decrement heap_size.
5. Call Max-Heapify on the root (index 1).
6. Return stored maximum.

Time: $O(\log n)$ — constant work plus one Max-Heapify call.

The swap with the last element preserves the structural property (only the rightmost bottom element can be removed without breaking completeness). The heap property is fixed by bubbling the new root downwards.

Increase-Key (Bubble-Up)

Purpose: Increase the value of a key at position $i$, then restore the heap property by moving it upward.

Algorithm:

1. If new value < current value, error.
2. Set $A[i]$ to new value.
3. While $i > 1$ and $A[i] > A[\text{parent}(i)]$:
4.  Swap $A[i]$ and $A[\text{parent}(i)]$.
5.  $i = \text{parent}(i)$.

Time: $O(\log n)$.

Max-Peek

Simply return $A[1]$ in $O(1)$ time. No modification to the heap.

Operations Summary

Operation	Purpose	Time	Method
Max-Heapify	Fix a single violation	$O(\log n)$	Bubble down
Insert	Add new element	$O(\log n)$	Add at end, bubble up
Extract-Max	Remove and return max	$O(\log n)$	Swap with last, bubble down
Increase-Key	Update to larger value	$O(\log n)$	Update, bubble up
Max-Peek	View maximum	$O(1)$	Read $A[1]$

All operations rely on the heap height being $\lfloor \log_2 n \rfloor$, ensuring each upward or downward traversal touches at most $O(\log n)$ nodes.