BinaryHeap: An Implicit Binary Tree

Heaps overview

Here, we discuss two implementations of the extremely useful priority Queue data structure. Both of these structures are a special kind of binary tree called a heap, which means “a disorganized pile.” This is in contrast to binary search trees that can be thought of as a highly organized pile.

The first heap implementation uses an array to simulate a complete binary tree. This very fast implementation is the basis of one of the fastest known sorting algorithms, namely heapsort. The second implementation is based on more flexible binary trees. It supports a meld(h) operation that allows the priority queue to absorb the elements of a second priority queue h.

BinaryHeap: an implicit binary tree

Our first implementation of a (priority) Queue is based on a technique that is over four hundred years old. Eytzinger’s method allows us to represent a complete binary tree as an array by laying out the nodes of the tree in breadth-first order. In this way, the root is stored at position 0, the root’s left child is stored at position 1, the root’s right child at position 2, the left child of the left child of the root is stored at position 3, and so on.

If we apply Eytzinger’s method to a sufficiently large tree, some patterns emerge. The left child of the node at index i is at index left(i) = 2i + 1 and the right child of the node at index i is at index right(i) = 2i+ 2. The parent of the node at index i is at index parent(i) = (i − 1)/2.

A BinaryHeap uses this technique to implicitly represent a complete binary tree in which the elements are heap-ordered: the value stored at any index i is not smaller than the value stored at index parent(i), with the exception of the root value, i = 0. It follows that the smallest value in the priority Queue is therefore stored at position $0$ ...