Max-Heap

data-structures algorithms

Definition

Max-Heap

A max-heap is a heap that satisfies the max-heap property: for every node $i$ other than the root, the value of the parent is at least the value of the node itself:

$$A[\mathrm{parent}(i)]\ge A[i]$$

Consequently, the largest element in a max-heap is always stored at the root, and the values in any path from the root to a leaf are in non-increasing order.

Operations

Max-Heapify

The $max-heapify$ procedure is essential for maintaining the max-heap property. Given an array $A$ and an index $i$, it assumes that the binary trees rooted at $\mathrm{left}(i)$ and $\mathrm{right}(i)$ are already max-heaps, but that $A[i]$ might be smaller than its children.

Extract Max

To extract the maximum element:

1. Copy the root value (the maximum).
2. Replace the root with the last element in the array.
3. Decrease the heap size.
4. Call $max-heapify$ on the root to restore the heap property.

Insert

To insert a new element $x$:

1. Add $x$ at the end of the heap (the next available leaf position).
2. “Bubble up” (or $increase-key$): compare $x$ with its parent and swap if $x$ is larger, repeating until the max-heap property is satisfied.

Complexity

The time complexity for max-heap operations depends on the height $h=\lfloor \log n\rfloor$ of the tree:

• Max-Heapify: $O(\log n)$
• Insert: $O(\log n)$
• Extract-Max: $O(\log n)$
• Build-Max-Heap: $O(n)$