Heaps

Binary Heap

• A binary heap is a nearly complete binary tree stored in an array $A[\mathrm{1...}n]$ that satisfies:
  • Structure property: the tree is a complete binary tree (every level is filled except possibly the last; filled from left to right)
  • Order property:
    • Max-heap: for every node $i$ other than the root, $A[parent(i)]\ge A[i]$
    • Min-heap; for every node $i$ other than the root, $A[parent(i)]\le A[i]$
• In a max-heap, the maximum is at $A[1]$, in a min-heap, the minimum is at $A[1]$ (the root).
• Using 1-based indexing:
  • $parent(i)=\lfloor \frac{i}{2}\rfloor$
  • $left(i)=2i$
  • $right(i)=2i+1$
• The height $h$ of a heap with $n$ nodes is $\lfloor \lg n\rfloor$

Key functions

MAX-HEAPIFY

Goal: to fix a single possible violation at node $i$, assuming its children’s subtrees already satisfy the max heap property.

MAX-HEAPIFY(A, i):
    l ← left(i)
    r ← right(i)
    largest ← i
    if l ≤ A.heap_size and A[l] > A[largest]:
        largest ← l
    if r ≤ A.heap_size and A[r] > A[largest]:
        largest ← r
    if largest ≠ i:
        swap A[i], A[largest]
        MAX-HEAPIFY(A, largest)

def max_heapify(A, i, heap_size):
    left = 2 * i + 1
    right = 2 * i + 2
    largest = i
 
    if left < heap_size and A[left] > A[largest]:
        largest = left
    if right < heap_size and A[right] > A[largest]:
        largest = right
 
    if largest != i:
        A[i], A[largest] = A[largest], A[i]
        max_heapify(A, largest, heap_size)
 

• Running time. At most the height of the node $O(\lg n)$. A common bound uses the recurrence $T(n)\le T(2n/3)+\Theta (1)$ since the violating element moves into a subtree of size at most $2n/3$, giving $T(n)=O(\lg n)$

BUILD-MAX-HEAP

Converts an array into a max-heap by calling MAX-HEAPIFY in a bottom-up manner.

BUILD-MAX-HEAP(A):
    A.heap_size ← length(A)
    for i ← ⌊length(A)/2⌋ downto 1:
        MAX-HEAPIFY(A, i)

def build_max_heap(A):
    heap_size = len(A)
    # Start from the last non-leaf node and go upwards
    for i in range((heap_size // 2) - 1, -1, -1):
        max_heapify(A, i, heap_size)

It is actually $O(n$).

HEAPSORT

Use the heap as a selection data structure:

1. Build a max-heap on the array
2. Repeatedly swap the maximum at the root with the last element in the heap, shrink the heap and restore the heap with MAX-HEAPIFY

HEAPSORT(A):
    BUILD-MAX-HEAP(A)
    for i ← length(A) downto 2:
        swap A[1], A[i]
        A.heap_size ← A.heap_size - 1
        MAX-HEAPIFY(A, 1)

Priority Queues