12.6.1. 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 heap 1 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.

1

Note that the term “heap” is also sometimes used to refer to free store.

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 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 use 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 max heaps. The class uses records that support the Comparable interface to provide flexibility.

// Max-heap implementation
// use `java -ea` to enable assertions that check valid heap positions
class MaxHeap {
  private Comparable[] heap; // Pointer to the heap array
  private int maxSize; // Maximum size of the heap
  private int n; // Number of things now in heap

  // Constructor supporting preloading of heap contents
  MaxHeap(Comparable[] h, int heapSize, int max) {
    heap = h;
    n = heapSize;
    maxSize = max;
    buildHeap();
  }

  // Return current size of the heap
  public int heapSize() { return n; }

  // Return true if pos a leaf position, false otherwise
  public boolean isLeaf(int pos) 
  { return (n / 2 <= pos ) && (pos < n); }

  // Return position for left child of pos
  public static int leftChild(int pos) 
  { return 2 * pos + 1; }

  // Return position for right child of pos
  public static int rightChild(int pos) 
  { return 2 * pos + 2; }

  // Return position for parent
  public static int parent(int pos) 
  { return (pos - 1) / 2; }

  // Insert val into heap
  public void insert(Comparable key) {
    assert n < maxSize : "Heap is full; cannot insert";
    heap[n] = key;
    n++;
    siftUp(n - 1);
  }

  // Heapify contents of Heap
  private void buildHeap() {
    for (int i = parent(n - 1); i >= 0; i--) {
      siftDown(i);
    }
  }

  // Moves an element down to its correct place
  private void siftDown(int pos) {
    assert (0 <= pos && pos < n) : "Invalid heap position";
    while (!isLeaf(pos)) {
      int child = leftChild(pos);
      if ((child + 1 < n) && isGreaterThan(child + 1, child)) {
        child = child + 1; // child is now index with the greater value
      }
      if (!isGreaterThan(child, pos)) {
        return; // stop early
      }
      swap(pos, child);
      pos = child; // keep sifting down
    }
  }

  // Moves an element up to its correct place
  private void siftUp(int pos) {
    assert (0 <= pos && pos < n) : "Invalid heap position";
    while (pos > 0) {
      int parent = parent(pos);
      if (isGreaterThan(parent, pos)) {
        return; // stop early
      }
      swap(pos, parent);
      pos = parent; // keep sifting up
    }
  }

  // Remove and return maximum value
  public Comparable removeMax() {
    assert n > 0 : "Heap is empty; cannot remove";
    n--;
    swap(0, n);  // Swap maximum with last value
    siftDown(0); // Put new heap root val in correct place
    return heap[n];
  }

  // Remove and return element at specified position
  public Comparable remove(int pos) {
    assert (0 <= pos && pos < n) : "Invalid heap position";
    n--;
    swap(pos, n); // Swap with last value
    update(pos);  // Move other value to correct position
    return heap[n];
  }

  // Modify the value at the given position
  public void modify(int pos, Comparable newVal) {
    assert (0 <= pos && pos < n) : "Invalid heap position";
    heap[pos] = newVal;
    update(pos);
  }

  // The value at pos has been changed, restore the heap property
  private void update(int pos) {
    siftUp(pos);   // priority goes up
    siftDown(pos); // unimportant goes down
  }

  // swaps the elements at two positions
  private void swap(int pos1, int pos2) {
    Comparable temp = heap[pos1];
    heap[pos1] = heap[pos2];
    heap[pos2] = temp;
  }

  // does comparison used for checking heap validity
  private boolean isGreaterThan(int pos1, int pos2) {
    return heap[pos1].compareTo(heap[pos2]) > 0;
  }
}

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).

Method heapsize returns the current size of the heap. H.isLeaf(pos) returns TRUE if position pos is a leaf in heap H, and FALSE otherwise. Members leftchild, rightchild, and parent 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 insert will insert a new element \(V\) into the heap.

Settings

Saving...
Server Error
Resubmit

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 insert, it must take up the first \(n+1\) positions after. To accomplish this, insert 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 insert 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.

12.6.2. Building a Heap¶

If all \(n\) values are available at the beginning of the building process, we can build the heap faster than just inserting the values into the heap one by one. Consider this example, with two possible ways to heapify an initial set of values in an array.

Settings

Saving...
Server Error
Resubmit

Figure 12.6.1: Two series of exchanges to build a max heap. (a) This heap is built by a series of nine exchanges in the order (4-2), (4-1), (2-1), (5-2), (5-4), (6-3), (6-5), (7-5), (7-6). (b) This heap is built by a series of four exchanges in the order (5-2), (7-3), (7-1), (6-1).

From this example, it is clear that the heap for any given set of numbers is not unique, and we see that some rearrangements of the input values require fewer exchanges than others to build the heap. So, how do we pick the best rearrangement?

One good algorithm stems from induction. Suppose that the left and right subtrees of the root are already heaps, and \(R\) is the name of the element at the root. This situation is illustrated by this figure:

In this case there are two possibilities.

1. \(R\) has a value greater than or equal to its two children. In this case, construction is complete.

2. \(R\) has a value less than one or both of its children.

\(R\) should be exchanged with the child that has greater value. The result will be a heap, except that \(R\) might still be less than one or both of its (new) children. In this case, we simply continue the process of “pushing down” \(R\) until it reaches a level where it is greater than its children, or is a leaf node. This process is implemented by the private method siftdown.

This approach assumes that the subtrees are already heaps, suggesting that a complete algorithm can be obtained by visiting the nodes in some order such that the children of a node are visited before the node itself. One simple way to do this is simply to work from the high index of the array to the low index. Actually, the build process need not visit the leaf nodes (they can never move down because they are already at the bottom), so the building algorithm can start in the middle of the array, with the first internal node.

Here is a visualization of the heap build process.

Settings

Saving...
Server Error
Resubmit

Method buildHeap implements the building algorithm.

What is the cost of buildHeap? Clearly it is the sum of the costs for the calls to siftdown. Each siftdown operation can cost at most the number of levels it takes for the node being sifted to reach the bottom of the tree. In any complete tree, approximately half of the nodes are leaves and so cannot be moved downward at all. One quarter of the nodes are one level above the leaves, and so their elements can move down at most one level. At each step up the tree we get half the number of nodes as were at the previous level, and an additional height of one. The maximum sum of total distances that elements can go is therefore

The summation on the right is known to have a closed-form solution of approximately 2, so this algorithm takes \(\Theta(n)\) time in the worst case. This is far better than building the heap one element at a time, which would cost \(\Theta(n \log n)\) in the worst case. It is also faster than the \(\Theta(n \log n)\) average-case time and \(\Theta(n^2)\) worst-case time required to build the BST.

Settings

Saving...
Server Error
Resubmit

12.6.3. Removing from the heap or updating an object’s priority¶

Settings

Saving...
Server Error
Resubmit

Because the heap is \(\log n\) levels deep, the cost of deleting the maximum element is \(\Theta(\log n)\) in the average and worst cases.

Settings

Saving...
Server Error
Resubmit

For some applications, objects might get their priority modified. One solution in this case is to remove the object and reinsert it. To do this, the application needs to know the position of the object in the heap. Another option is to change the priority value of the object, and then update its position in the heap. Note that a remove operation implicitly has to do this anyway, since when the last element in the heap is swapped with the one being removed, that value might be either too small or too big for its new position. So we use a utility method called update in both the remove and modify methods to handle this process.

12.6.4. Priority Queues¶

The heap is a natural implementation for the priority queue discussed at the beginning of this section. Jobs can be added to the heap (using their priority value as the ordering key) when needed. Method removemax can be called whenever a new job is to be executed.

Some applications of priority queues require the ability to change the priority of an object already stored in the queue. This might require that the object’s position in the heap representation be updated. Unfortunately, a max heap is not efficient when searching for an arbitrary value; it is only good for finding the maximum value. However, if we already know the index for an object within the heap, it is a simple matter to update its priority (including changing its position to maintain the heap property) or remove it. The remove method takes as input the position of the node to be removed from the heap. A typical implementation for priority queues requiring updating of priorities will need to use an auxiliary data structure that supports efficient search for objects (such as a BST). Records in the auxiliary data structure will store the object’s heap index, so that the object’s priority can be updated. Priority queues can be helpful for solving graph problems such as single-source shortest paths and minimal-cost spanning tree.

For a story about Priority Queues and dragons, see Computational Fairy Tales: Stacks, Queues, Priority Queues, and the Prince's Complaint Line.