Heaps

Overview

The binary heap data structure is an array object that can be viewed as a complete binary tree.

The primary function used to maintain the max-heap property is MAX_HEAPIFY_DOWN. This function assumes the left and right- subtrees at a given node are max heaps but that the current node may be smaller than its children. An analagous function and assumptions exist for MIN_HEAPIFY_DOWN.

inline int left_child(int i) { return (i << 1) + 1; }
inline int right_child(int i) { return (i << 1) + 2; }
 
void max_heapify_down(int n, int H[static n], int i) {
  while (true) {
    int lc = left_child(i);
    int rc = right_child(i);
    int next = i;
 
    if (lc < n && H[next] < H[lc]) {
      next = lc;
    }
    if (rc < n && H[next] < H[rc]) {
      next = rc;
    }
    if (next == i) {
      return;
    }
    swap(H, i, next);
    i = next;
  }
}
 
void build_max_heap(int n, int H[static n]) {
  for (int i = n / 2 - 1; i >= 0; --i) {
    max_heapify_down(n, H, i);
  }
}

Bibliography

• Thomas H. Cormen et al., Introduction to Algorithms, Fourth edition (Cambridge, Massachusett: The MIT Press, 2022).