Heaps

Binary Heap

The most basic and common variant of the heap data structure is the binary heap. There are two subvariants — the min binary heap (minBH, the tree to the left), and the max binary heap (maxBH, the tree to the right).

In a maxBH, the parent nodes are always greater than the child nodes. The inverse is true for the minBH — the parent nodes are always smaller than the child nodes. As their names imply, for both the maxBH and minBH, each node can have at most two children.

There are two key differences between binary heaps and binary search trees. First, there is no inherent order; all that matters are the parent-child relationships. An informal way to think about it: Binary heaps answer who gets on the lifeboat first when the ship sinks. In minBH, it's the children — a child is always worth more than its parent. And in maxBH, it's the parents — a parent is always worth more than its child.

Second, binary heaps are as compact as possible. Each generation is filled as much as possible before moving to the next generation, with left children filled out first. This requirement's purpose is to use space efficiently.

An important point to note about the binary heaps. Consider the following maxBH:

The two nodes, n(21) and n(34), are not necessarily the largest numbers in the entire maxBH. Notice the node n(25). Again, this stems from the fact that there's no inherent order. We're just looking at the parent-child relationships.

Representing Heaps

Consider the following maxBH:

If we performed a breadth-first traversal of this tree, storing each visited node's value in an array, we would get the following:

Notice the relationship between the index of each node and the indices of its children:

Examining these arrays, we would can see that, given a node ${n}$ with index ${i_n,}$ its left-child has the index ${\ell}$ and its right child has the index ${r,}$ yielded by the formulas:

We can draw additional observations from these formulas. First, the left-child of a node has the form:

where ${n \in \uint^{+}.}$ From number theory, this implies that the number will always be odd. Accordingly, the left child of a given node in a binary heap will always have an odd number index when placed in an array via breadth-first traveral. Second, we see that the index of a given node's right-child has the form:

where ${n \in \uint^{+}.}$ Given that ${n}$ is a positive integer, the closure property of the positive integers implies that the index can be expressed as:

where ${k \in \uint^{+}.}$ And again from number theory, this implies that the right-child's index will always be an even number. Accordingly, the right-child of a given node in a binary heap will always have an even number index when placed in an array via breadth-first traversal.

Following these inferences, if we're given the breadth-first traversal sequence of a binary heap, we can determine the parent of a given node ${n}$ with the following lemma:

lemma. Let ${n}$ be an element with the index ${i}$ in the breadth-first traversal sequence of some binary heap. The index of the parent of ${n,}$ denoted ${p,}$ is given by the following formula:

$$p = \begin{cases} \dfrac{i-1}{2} ~~~~ i \in \Z_{\text{odd}} \\[2em] \dfrac{i}{2} - 1 ~~~~ i \in \Z_{\text{even}} \end{cases}$$

Examining these two formulas, we see that the only difference between the two is when to decrement by ${1.}$ For odd indices, we decrement then divide by two, and for even indices, we divide by two then decrement by ${1.}$ This set of conditions is encapsulated in the floor function. Accordingly, we can generalize the formula:

lemma. Let ${n}$ be an element with the index ${i}$ in the breadth-first traversal sequence of some binary heap. The index of the parent of ${n,}$ denoted ${p,}$ is given by the following formula:

$$p = \left\lfloor \dfrac{n-1}{2} \right\rfloor$$

Just to verify that this formula is correct, let's look at the original sequence again alongside the tree:

For the node n(15), the index of its parent is:

The node at index ${3}$ is n(17). Examining the tree, we see that the n(17) is, in fact, the parent of n(15).

Implementing maxBH

Implementing maxBH is fairly straightforward:

class MaxBinaryHeap {
	constructor:
		nodes = [];
	methods:
		insert(newNode) {
			append(this->nodes, newNode);
			let newNodeIndex = lengthOf(this->nodes) - 1;
			let parentIndex = ⌊((newNodeIndex - 1) / 2)⌋; // floor
			while (this->nodes[parentIndex] < this->nodes[index]) {
				swapArrayElements(this->nodes, parentIndex, newNodeIndex);
				newNodeIndex = parentIndex;
			}
		}
}

This procedure uses the process of bubbling up. When we insert a new node to the binary heap, we continue swapping the new node with the node at the parent index until we reach a point where the node at the parent index is greater than the new node's value.

import swap from "../../../../utilities/swap.js";
import floor from "../../../../utilities/floor.js";
import append from "../../../../utilities/append.js";


class MaxBinaryHeap {
	constructor() {
		this.values = [];
	}
	bubbleUp(val) {
		append(this.values, val);
		let index = this.values.length - 1;
		let parentIndex = floor((index - 1) / 2);
		while (this.values[parentIndex] < this.values[index]) {
			swap(this.values, parentIndex, index);
			index = parentIndex;
		}
		return this;
	}

Removing from a Heap

The heap's root is the most commonly removed, or replaced, node:

Recall that with max binary heap, the largest element is always at the top. Accordingly, when we remove from a max binary heap, we always the next largest element to rise to the top.

To illustrate, suppose we removed the top most node:

The next step is to take the smallest element, and place it as the root. In this case, that's the node containing 12:

Next, we perform a procedure called down-bubbling.¹ We compare the current root against its children. In this case, the node containing 39, and the node containing 33:

Comparing these two children, we take whichever is larger, and swap it with the current root. Here, the larger child is 39, so we swap 12 into 39's position:

Now that 12 is in a new position, we compare 12 against its new children — 18 and 27. 27 is larger, so we swap:

Notice that 12 has sunk down to its correct place. Our tree is complete. The procedure is as follows:

1. Go to the first value in the values array.
2. Swap the first value with the last value in the array.
3. Save the last value in some variable ${v.}$
4. Remove the last item.
5. Begin bubble-down:
   1. Let the parent index ${i}$ start at 0 (the root).
   2. Compute the index of the root's left-child.
      $$2(i + 1)$$
   3. Compute the index of the root's right-child.
      $$2(i + 2)$$
   4. If the left- or right-child is greater than the root, swap.
   5. If both the left- and right-child are greater, swap the largest child.
   6. If neither the left- nor the right-children are greater, go to step 6.
   7. The index of the child swapped is now the new parent index.
6. Return the old root, earlier stored in some variable ${v.}$

bubbleDown() {
	let idx = 0;
	const length = this.values.length;
	const element = this.values[0];
	let swap = null;
	let leftChild, rightChild;
	let leftChildIndex, rightChildIndex;
	while (true) {
		leftChildIndex = 2 * idx + 1;
		rightChildIndex = 2 * idx + 2;

		if (leftChildIndex < length) {
			leftChild = this.values[leftChildIndex];
			if (leftChild > element) {
				swap = leftChildIndex;
			}
		}

		if (rightChildIndex < length) {
			rightChild = this.values[righChildIndex];
			if (
				(swap===null && rightChild > element) ||
				(swap !== null && rightChild > leftChild)) {
					swap = rightChildIndex;
				}
		}

		if (swap === null) break;
		this.values[idx] = this.values[swap];
		this.values[swap] = element;
		idx = swap;
	}
}

extractMax() {
	const max = this.values[0];
	const end = this.values.pop();
	this.values[0] = end;
	this.bubbleDown();
	return max;
}