Heaps

A heap is an array that is interpreted as a nearly complete binary tree: for a heap $H$, $H[0]$ is the root of tree, $H[1]$ is the left child of root, $H[2]$ is the right child of the root, $H[3]$ is the left child of the left child of the root, and so on and so forth for the size of the array.

struct Heap {
  int size;
  int array[HEAP_SIZE];
}

int parent(int i) {
  return i / 2;
}

int left(int i) {
  return 2 * i;
}

int right(int i) {
  return 2 * i + 1
}

Heaps have a heap property: in a max-heap, the property is that for every node $i$ other than the root,

$H[PARENT(i)]\; \ge \; H[i]$

aka the value of any node is at most the value of it's parent. A min-heap is the reverse.

The height of a heap is the height of the binary tree the heap represents. For an array of $n$ elements, a heap's height is $O(log\; n)$.

A heapify algorithm maintains a heap's heap property. It's called with a heap and an index to start at, and assumes that the sub-heaps to the left and right of the index maintain the heap propery, but that $H[i]$ might not:

void max_heapify(struct Heap h, int i) {
  int left = left(i);
  int right = right(i);
  int largest = -1;

  if (left < heap.size + 1 &&
      heap.array[left] > heap.array[i])
    largest = left;
  else if (right < heap.size + 1 &&
      h.array[right] > h.array[largest])
    largest = right;
  else
    largest = i;
    
  if (largest != i) {
    int temp = heap.array[i];
    heap.array[i] = heap.array[largest];
    heap.array[largest] = temp;
    max_heapify(h, largest);
  }
}

The runtime of max_heapify is $O(log\; n)$ or $O(h)$ (for height $h$), and the proof is complicated enough I'm not going to get into it here.

We can convert an array of $n$ elements into a max-heap with build_max_heap:

void build_max_heap(struct Heap h, int n) {
  h.size = n;
  for (int i = h.size / 2; i > 0; i--)
    max_heapify(h, i);
}

The elements in the array from $(n/2)\; +\; 1$ to $n$ are all leaves, which are essentially 1-element heaps already. build_max_heap actually takes $O(n)$, the proof for which is complicated enough that I'm not going to get into it here.