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.

Heapify-Up

Heapify-up

In a max-heap, heapify-up restores the heap property after inserting a new value at the end of the array. The new value is compared with its parent, and it is swapped upwards while it is larger than the parent.

Heapify-Down

Heapify-down

In a max-heap, heapify-down restores the heap property after the root has been replaced by the last element in the array. The node is compared with its larger child, and it is swapped downwards while it is smaller than that child.

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)$