Heaps

A priority queue is an abstract data structure. Abstract here means that there can be multiple different (concrete) implementations, each with their own advantages.

A priority queue maintains a set S of elements, and requires the following operations:

insert(S, x)

add the element x into the set

get_max(S)

return the element with the largest key

pop_max(S)

same as get_max(S), but also delete the returned element from the set

The following are additional operations that may be useful depending on the application:

increase_key(S, x, k)

increases the value of x's key to k (assumed to be at least as large as x's current key value)

merge(S1, S2)

merge two sets together

We use the word key to mean "a standard unit of measurement that is comparable and which is present for every node in the set".

Heaps are concrete data structures typically used to implement priority queues, because they are a natural fit. They have the best performance compared to other alternatives.

Heaps are a tree-based data structure, that come in two (symmetric) flavors: max-heaps and min-heaps. Max-heaps have the following heap property: child nodes cannot be greater than its parent (nodes get smaller as you go down each level of the tree). In a min-heap, it's the opposite: child nodes cannot be smaller than its parent (nodes get bigger as you go down each level of the tree).

Note that heaps could technically be implement using any type of tree, but in practice binary trees are used because they are the simplest (they have the minimum number of children at each node to be considered a tree).

The simplest way to implement a priority queue (without a heap) is to just use a sorted array. The get_max() and pop_max() operations are just array lookups at the end of the sorted array.

The insert() operation would be slow though, because we'd have to make sure to insert the element in the correct (sorted) location.

class MaxHeapBruteForce:
    def __init__(self):
        self.items = []
        self._count = 0

    def __len__(self):
        return self._count

    # Insertion is slow because we have to sort all items *every* time.
    def insert(self, x: Any):
        self.items.append(x)
        self.items.sort()
        self._count += 1

    def get_max(self) -> Any:
        if self._count == 0:
            raise IndexError("get from an empty heap")

        return self.items[-1]

    def pop_max(self) -> Any:
        if self._count == 0:
            raise IndexError("pop from an empty heap")

        max = self.items[-1]
        self.items = self.items[:-1]
        self._count -= 1

        return max

The only downside is the slow speed of insert(). The other functions get_max() and pop_max() are straightforward enough.

We can use a standard binary tree data structure, but make sure to always fill it up left-to-right at every level (and only move down to the next level when we're out of room at the current level). This way, we can minimize the depth of the tree. These types of binary trees are called complete binary trees.

Why do we want to minimize the depth of the tree? It's because that way, we can minimize the depth of the heap as we grow it. Minimizing depth is important because it minimizes the cost of insert() and pop_max().

We won't be implementing a tree-based heap though, mainly because in order to do so we need to be able to go up to a parent node from a child node, and our existing binary trees implementation's nodes only has links to its children, not its parent.

Did you know that you could represent complete binary trees using an array? All you have to do is make sure to store each level of the tree contiguously in the array, with the upper levels on the left and the lower levels on the right.

Array indices:
1 2 3 4 5 6 7 8 9 ...

Tree representation:

              1
     2                 3
4         5       6         7

We use 1-based indexing, because it makes the conversion between an array index and its location in the binary tree a little bit easier. Using the above scheme, it becomes easy to both represent the location of the array index in the binary tree, and also to figure out which index is the parent or left/right child.

Consider the index 3. Its binary representation (this is the crux of the scheme) is 11. We ignore the high-order bit (that is, the leftmost bit) to get just 1. The "1" here means "go right" (and "0" means "go left"). The children of 3 are 6 and 7. We just tack on an additional 0 and 1 to the original 11 to get the children (110 and 111). Again we ignore the leftmost bit, and arrive at 10 and 11, which mean "right, left" and "right, right" from the root node, respectively.

In summary we use binary digits to mean "go left" (0) or "go right" (1), and if we use 0-based indexing we can very easily associate a binary number with a position in the binary tree. This scheme is the one we used in our binary trees implementation to specify "directions" for figuring out the location of the node in the overall tree.

For the following reasons, this array-based implementation is considered to be the optimal implementation for most scenarios:

Space-efficient

No need to store links to other nodes — every node just sits in an array.

Cache-friendly

Arrays live in contiguous blocks of memory, and are easier to load into (and stay in) the CPU's cache. Trees store links, and links can lead to random locations in memory, and are therefore less cache-friendly.

O(1) access to all nodes

Because we use an array, accessing any node in the heap takes constant time; contrast this with a tree-based heap that must jump through links starting from the root to get to the desired node.

Easy to know where the "end" of the heap is

The place where we can insert a new item in the node is just right of the last element in the array, and can be accessed in O(1) time.

class MaxHeap:
    optimal_max_heap_methods

class MinHeap(MaxHeap):
    optimal_min_heap_methods

The min-heap (MinHeap) is just a symmetric mirror of the max-heap. As such, we inherit from MaxHeap to reduce code duplication.

Check that we can use the heap to sort items (aka "heapsort"). We also check that the optimal version agrees with the brute force version.

@given(st.lists(st.integers(min_value=1, max_value=1000),
                min_size=1,
                max_size=50))
def test_heap_sort(self, to_insert: list[int]):
    max_heap_bf = MaxHeapBruteForce()
    max_heap_optimal = MaxHeap()
    self.assertEqual(len(max_heap_bf), len(max_heap_optimal))

    # Populate heaps.
    for item in to_insert:
        max_heap_bf.insert(item)
        max_heap_optimal.insert(item)
    self.assertEqual(len(max_heap_bf), len(max_heap_optimal))

    # Drain heaps.
    output_bf = []
    output_optimal = []
    for _ in range(len(to_insert)):
        x = max_heap_bf.pop_max()
        y = max_heap_optimal.pop_max()
        output_bf.append(x)
        output_optimal.append(y)
    self.assertEqual(output_bf, output_optimal)
    self.assertEqual(len(max_heap_bf), len(max_heap_optimal))

    # Are the outputs sorted (in reverse, because it's a max-heap)?
    s = list(sorted(to_insert))
    self.assertEqual(s, list(reversed(output_bf)))
    self.assertEqual(s, list(reversed(output_optimal)))

For our MinHeap implementation, check that it performs the same way as Python's heapq module (which implements a min-heap).

@given(st.lists(st.integers(min_value=1, max_value=1000),
                min_size=1,
                max_size=50))
def test_min_heap(self, to_insert: list[int]):
    min_heap = MinHeap()
    min_heap_std: List[int] = []

    # Populate heaps.
    for item in to_insert:
        min_heap.insert(item)
        heapq.heappush(min_heap_std, item)
    self.assertEqual(len(min_heap), len(min_heap_std))

    # Drain heaps.
    output = []
    output_std = []
    for _ in range(len(to_insert)):
        x = min_heap.pop_min()
        y = heapq.heappop(min_heap_std)
        output.append(x)
        output_std.append(y)

    # Check drained output (should be in agreement with heapq output).
    self.assertEqual(output, output)
    self.assertEqual(len(min_heap), len(min_heap_std))