7.2 Heaps and Priority Queues

There are many situations, both in real life and in computing applications, where we wish to choose the next “most important” from a collection of people, tasks, or objects. For example, doctors in a hospital emergency room often choose to see next the “most critical” patient rather than the one who arrived first. When scheduling programs for execution in a multitasking operating system, at any given moment there might be several programs (usually called jobs) ready to run. The next job selected is the one with the highest priority. Priority is indicated by a particular value associated with the job (and might change while the job remains in the wait list).

When a collection of objects is organized by importance or priority, we call this a priority queue. A normal queue data structure will not implement a priority queue efficiently because search for the element with highest priority will take $\Theta(n)$ time. A list, whether sorted or not, will also require $\Theta(n)$ time for either insertion or removal. A BST that organizes records by priority could be used, with the total of $n$ inserts and $n$ remove operations requiring $\Theta(n \log n)$ time in the average case. However, there is always the possibility that the BST will become unbalanced, leading to bad performance. Instead, we would like to find a data structure that is guaranteed to have good performance for this special application.

This section presents the binary heap data structure. A heap is defined by two properties. First, it is a complete binary tree, so heaps are nearly always implemented using the array representation for complete binary trees. Second, the values stored in a heap are partially ordered. This means that there is a relationship between the value stored at any node and the values of its children. There are two variants of the heap, depending on the definition of this relationship.

A max heap has the property that every node stores a value that is greater than or equal to the value of either of its children. Because the root has a value greater than or equal to its children, which in turn have values greater than or equal to their children, the root stores the maximum of all values in the tree.

A min heap has the property that every node stores a value that is less than or equal to that of its children. Because the root has a value less than or equal to its children, which in turn have values less than or equal to their children, the root stores the minimum of all values in the tree.

Note that there is no necessary relationship between the value of a node and that of its sibling in either the min heap or the max heap. For example, it is possible that the values for all nodes in the left subtree of the root are greater than the values for every node of the right subtree. We can contrast BSTs and heaps by the strength of their ordering relationships. A BST defines a total order on its nodes in that, given the positions for any two nodes in the tree, the one to the “left” (equivalently, the one appearing earlier in an inorder traversal) has a smaller key value than the one to the “right”. In contrast, a heap implements a partial order. Given their positions, we can determine the relative order for the key values of two nodes in the heap only if one is a descendant of the other.

Min heaps and max heaps both have their uses. For example, the Heapsort algorithm uses the max heap, while the Replacement Selection algorithm used for external sorting uses a min heap. The examples in the rest of this section will sometimes use a min and sometimes a max heap.

Be sure not to confuse the logical representation of a heap with its physical implementation by means of the array-based complete binary tree. The two are not synonymous because the logical view of the heap is actually a tree structure, while the typical physical implementation uses an array.

Here is an implementation for min heaps. It uses a dynamic array list that will resize automatically when the number of elements change.

class MinHeap implements PriorityQueue:
    MinHeap():
        this.heap = new DynamicArrayList()

    getMin():
        // Returns the minimum element, without removing it.
        precondition: this.heap.size() > 0
        return this.heap[0]

    add(elem):
        // Adds an element to the priority queue.
        i = this.heap.size()
        this.heap.add(i, elem)  // Add the element at end of the heap.
        this.siftUp(i)          // Put it in its correct place.

    removeMin():
        // Removes and returns the minimum element.
        precondition: this.heap.size() > 0
        removed = this.heap[0]
        i = this.heap.size() - 1
        last = this.heap.remove(i)  // Find and remove the last element.
        if this.heap.size() > 0:
            this.heap[0] = last     // Replace the root with the last element.
            this.siftDown(0)        // Put the new root in its correct place.
        return removed

    siftDown(pos):
        // Sift a value down the tree, return its new position.
        heapSize = this.heap.size()
        while not this.isLeaf(pos):
            child = this.getLeftChild(pos)
            right = child + 1   // or: this.getRightChild(pos)
            if right < heapSize and this.heap[right] < this.heap[child]:
                child = right   // 'child' is now the index of the child with smaller value
            if this.heap[child] >= this.heap[pos]:
                return pos
            this.swap(pos, child)
            pos = child   // Move down one level in the tree.
        return pos

    siftUp(pos):
        // Sift a value up the tree, return its new position.
        while pos > 0:
            parent = this.getParent(pos)
            if this.heap[pos] >= this.heap[parent]:
                return pos
            this.swap(pos, parent)
            pos = parent   // Move up one level in the tree.
        return pos

    isLeaf(pos):
        // Return true if pos is a leaf position.
        return pos >= this.heap.size() / 2

    getLeftChild(pos):
        // Return the position for the left child of the given node.
        return 2 * pos + 1

    getRightChild(pos):
        // Return the position for the right child of the given node.
        return 2 * pos + 2

    getParent(pos):
        // Return the position for the parent. Returns 0 if we're already at the root.
        return int((pos - 1) / 2)

    swap(pos1, pos2):
        // Swap the values in two positions.
        this.heap[pos1], this.heap[pos2] = this.heap[pos2], this.heap[pos1]

This class definition makes two concessions to the fact that an array-based implementation is used. First, heap nodes are indicated by their logical position within the heap rather than by a pointer to the node. In practice, the logical heap position corresponds to the identically numbered physical position in the array. Second, the constructor takes as input a pointer to the array to be used. This approach provides the greatest flexibility for using the heap because all data values can be loaded into the array directly by the client. The advantage of this comes during the heap construction phase, as explained below. The constructor also takes an integer parameter indicating the initial size of the heap (based on the number of elements initially loaded into the array) and a second integer parameter indicating the maximum size allowed for the heap (the size of the array).

The class contains some private auxiliary methods that are use when adding and removing elements from the heap: isLeaf(pos) returns true if position pos is a leaf in the tree, and false otherwise. Methods getLeftChild, getRightChild, and getParent return the position (actually, the array index) for the left child, right child, and parent of the position passed, respectively.

One way to build a heap is to insert the elements one at a time. Method add will insert a new element $V$ into the heap.

You might expect the heap insertion process to be similar to the insert function for a BST, starting at the root and working down through the heap. However, this approach is not likely to work because the heap must maintain the shape of a complete binary tree. Equivalently, if the heap takes up the first $n$ positions of its array prior to the call to add, it must take up the first $n+1$ positions after. To accomplish this, add first places $V$ at position $n$ of the array. Of course, $V$ is unlikely to be in the correct position. To move $V$ to the right place, it is compared to its parent’s value. If the value of $V$ is less than or equal to the value of its parent, then it is in the correct place and the insert routine is finished. If the value of $V$ is greater than that of its parent, then the two elements swap positions. From here, the process of comparing $V$ to its (current) parent continues until $V$ reaches its correct position.

Since the heap is a complete binary tree, its height is guaranteed to be the minimum possible. In particular, a heap containing $n$ nodes will have a height of $\Theta(\log n)$. Intuitively, we can see that this must be true because each level that we add will slightly more than double the number of nodes in the tree (the $i$ th level has $2^i$ nodes, and the sum of the first $i$ levels is $2^{i+1}-1$). Starting at 1, we can double only $\log n$ times to reach a value of $n$. To be precise, the height of a heap with $n$ nodes is $\lceil \log n + 1 \rceil$.

Each call to add takes $\Theta(\log n)$ time in the worst case, because the value being inserted can move at most the distance from the bottom of the tree to the top of the tree. Thus, to insert $n$ values into the heap, if we insert them one at a time, will take $\Theta(n \log n)$ time in the worst case.