1 Priority Queue ADT

In this section we introduced a new ADT called a priority queue. As a reminder, the queue ADT allows for insertion and removal where the only item that may be removed is the least frequently added (yielding the first in first out behavior). In this way, a queue operates like a checkout line at a store where each shopper joins the line behind the person who arrived before them so that the one who had been there the longest is the next to be served.

For a priority queue, instead of removing the least frequently added item, we will remove the most important item. We can think of this as a line where more important people are allowed to cut in front of less important people. For example, in an emergency room someone with an urgent need would see a doctor before someone with a less serious condition. In this case the urgency of the patient’s condition would determine the order that we service those waiting.

With this motivation, here’s how we’ll define the priority queue ADT:

  • Notion: A collection of items along with their priority levels
  • Operations:
    • insert: adds a new element into the priority queue along with a given priority value
    • extract: deletes and returns the most important element according to its priority value
    • increaseKey: changes the priority value of the given element to make it larger
    • decreaseKey: changes the priority value of the given element to make it smaller

Convention: By convention for priority queues we understand the item with the smallest priority value to be the most important, and it is therefore what gets returned by the extract operation. This comes from the idea that priorities are communicated as rankings in the English language, and so saying you’re my number one priority is saying you’re the most important to me. We can also define priority queues so that the item with the largest priority value is the most important with only trivial changes. Because of this convention, though, all the examples below consider the smaller priority values more important.

Analogy Limitation: There is one way that the emergency room and line cutting analogies are unlike the priority queue ADT. In both of these analogies it’s most likely going to be the case that among people with the same level of priority that they are serviced in first-in-first-out order. In a priority queue, however, we will allow for items with same priority to be extracted in any order.

1.1 Priority Queues Using Lists

Next we can look at some examples of data structures for priority queues. With the queue ADT, we were able to effectively use list-like approaches for designing out data structures, so let’s try that same thing here. This can give us to better understand the challenges of creating a priority queue data structure, and help us to see what we might need to do to improve upon some relatively more straight forward approaches.

1.1.1 Unsorted Array Priority Queue

First, let’s look at what we might do if we just store the elements (and priorities) in an unsorted array. In this case we might have a field that we could call back to indicate the index of the last item in the array. From here we could use the following algorithms for the priority queue ADT operations insert and extract:

  • insert: add the item and its priority into the array at the index referenced by back, resizing if necessary. Then increment back.
  • extract: iterating from index 0 of the array up through index back, save the index and priority of the item with the smallest priority seen so far. Return the corresponding item, and remove it from the array by shifting all elements after it over by 1 index.

Because we do not care to impose any kind of ordering of the elements in our array, our insert algorithm runs in constant time (amortized). However, because we have no indication for where we might find the item with smallest priority, the extract operation requires linear time.

1.1.2 Sorted Array Priority Queue

Because priority queues require removing items in a sorted order, perhaps we could improve our data structure by requiring the items be stored in descending order (largest priority value at index 0, smallest at index n-1). In this data structure we will also have the field back that indicates the index of the last item in the array (in this case this will be the one with the smallest priority value). Here’s what insert and extract might look like in this case:

  • insert: starting from index 0, check to see if the new item has higher priority than the one at that current index, if not then check the next index, repeat until we reach an item with lower priority or until we reach back. Next insert the new item at the current index by shifting all items after that index over by one position. Increment back. Resize if necessary.
  • extract: because we sorted in descending order, the index back has the minimum priority. Decrement the value of back and return the value at the index back.

Because we need to keep our array sorted, we need to be very careful about where we add values into our array, and so the running time of insert is linear time. On the other hand, extract requires only constant time because we know exactly where the element with minimum priority might be.

1.1.3 Lessons

From these two examples it appears that there’s a trade-off in our data structure design: stricter ordering makes insert harder and extract easier, more relaxed ordering makes insert easier and extract harder. This provides the insight for the binary heap data structure that we will soon introduce for priority queues. In a binary heap we will store our elements in an array, but they will be only somewhat ordered so that we can have sublinear running time for both insert and extract. Specifically, we will achieve running times of \Theta(\log n) for both insert and extract.

2 Binary Heap Data Structure

In implementation, our binary heap data structure will store elements in an array, but manipulate the positions of elements as if they were stored in a binary tree. In other words, it will be representing a tree using an array. To describe this data structure we will first describe it as a tree, then later describe how we represent the tree using an array.

2.1 The Shape of the Tree

Binary heaps have very strict requirements on the structure of the tree that stores the elements. Specifically, the structure property of a heap requires:

  • Every level of the tree be completely full before any items may be included on the next level
  • If the last level is only partially full, the items must be filled in from left to right (so for example the left child of the left-most node of the second from last level must be the first to be filled in).

There are two motives for this:

  1. This shape will help us to achieve the \Theta(\log n) worst case running times for insert and extract
  2. This shape will help us to represent the tree using an array

2.2 Somewhat Ordering the Array

In addition to requiring a particular shape to the tree, heaps also require restrictions on where certain values may appear. For a min heap (i.e. one where the most important element has the lowest priority value) the following property must be true of every node in the tree:

Min Heap Property: For every node in the tree, the priority value of that node must be less than or equal to that of its children.

This heap property ensures that for every node, the priority of the value held there is the smallest of all nodes in its subtree. This is because if there was any node within a subtree with a smaller priority value then that node or one of its ancestors must violate the heap property with its parent. Since this applies to all nodes, that implies that the overall root of the heap must contain the element with the smallest priority. Therefore this heap property gives us one of the advantages of a sorted array in that we know exactly where to find the most important item.

The heap property also doesn’t require our array to be too sorted. Note that the heap property only enforces a priority relationship between a node and any values in its subtree. It does not have any restrictions on how a node’s priority value might relate to those of nodes in different branches of the tree (e.g. cousin nodes or aunt/uncle nodes). The result here will be that it does not require too much effort to maintain the heap property when adding/removing items from the heap (at least, it requires much less effort than maintaining a total ordering). Namely, since the heap property can be checked by just checking how parents relate to children, the heap property ensures that we need to do only a constant number of operations per level of the tree to restore the heap property after any insert/extract operation. The shape property then guarantees that the tree will not have many levels. The combination of these two rules therefore enables our fast (\Theta(\log n)) running time for each operation.

2.3 The Tree Representation Using an Array

Now let’s discuss how we can represent our heap using an array. When you learned about binary trees in your prerequisite course, you likely used nodes where each stored the value it contains and then had a reference to two other nodes representing its left and right children. For heaps we will store our values in an array, and then identify a node’s left and right children by doing arithmetic on array indices.

To represent our heap as an array we will leverage the heap structure property. The structure property is so strict that all trees of the same size must have the same shape. This is because there is a unique position that must be added to accommodate that new node. To represent our tree using an array, we will designate that the position added when adding the ith node will be stored at index i. In summary, we can identify each node’s index by counting off one level at a time, and then left-to-right within a level. The structure property insures that this assignment will never skip nodes and will never skip array indices. We will always start the counting off from the root. We could decide to start that count with the number 0 (thereby putting the root at index 0 of the array), however the arithmetic we’ll need to apply to the array indices in order to navigate the tree is a bit easier if we start of with 1 instead (thereby not using index 0 of the array at all).

For a node at index i, here’s how we can calculate the index of the following other nodes in relation to i:

  • Its left child: 2i
  • Its right child: 2i+1
  • Its parent \lfloor \frac{i}{2}\rfloor
  • Its left sibling: i-1 (this requires that i is itself a right child)
  • Its right sibling: i+1 (this requires that i is itself a left child)

2.4 Insert and Extract Algorithms

Since we’ve fully described how we’re representing our data, let’s discuss our algorithms for the priority queue ADT operations.

2.4.1 Insert

When inserting an element, the structure property of heaps designates a unique position that must be created in the heap. Namely, if the last level of the heap is not full then after adding a new item the new position must be the leftmost available slot of that last level. If the last level of the heap is full, then the new position must be the leftmost on the next level.

While the structure property designates a specific new position, we cannot necessarily just put the new item there. The heap property requires each node’s priority be less than or equal to its children. It could be that the newly-added item has a priority smaller than the parent of the new position we were required to create. In this case, we must rearrange values of the heap in order to maintain the heap property.

The idea of our algorithm is as follows:

  1. Place the new item at the position dictated by the structure property
  2. Compare that item’s priority with that of it’s parent. If the new item has a lower priority than its parent then swap the new item’s position with that of its parent.
  3. Repeat the previous step (compare the new item with its parent, swap less than) until either the new item’s priority value is greater than or equal to its parent, or the new item becomes the new root.

2.4.2 Extract

When extracting, the priority queue ADT requires that the item in the root of the heap be the one removed. However, the structure property of the heap requires that the position that be removed from the tree is the right-most node on the bottom-most level. In order to reconcile this, we will take a similar approach to what we saw with insert – we will first make a change to satisfy the structure property, and then we’ll rearrange values to satisfy the heap property. So what we’ll the take the right-most item of the last level (i.e. the item in the position that must be eliminated), move that to become the new root (eliminating the item at the root, so that the tree contains all the correct elements), and then swap the item we just moved with its children until we’ve restored the heap property.

Here are the overall steps:

  1. Save the value of the current root
  2. Move the item in the last index of the array to index 1 (overwriting and taking the place of the old root)
  3. Compare the new roots priority with that of its children. If any child has a smaller priority than the parent, swap the parent with the smaller child.
  4. Repeat the previous step (if smaller than any child, swap with the smallest child) until either the value we’re moving is smaller than both of its children, or until it becomes a leaf in the tree.
  5. Return the saved value of the original root

2.4.3 Running time analysis

Now let’s look at the running time of these operations. When identifying the running time, we will use the number of items currently in the heap as our measure for input size (i.e. this will be the value n in our running time function). To measure the running time we will count comparisons (an operation where we compare the priorities of two items in the heap to detect which is larger/smaller).

When inserting, in the worst case the newly added item will become the new root of the heap. In this case the item will be compared to each of its ancestors (nodes along the path from the root to the original location of the new node) exactly once. This means that the number of comparisons will be linear in the height of the tree.

We see a similar story when extracting. In the worst case the item moved to the root will end up back on the deepest level of the heap. In this case the item will be compared to each node along the path from the root to the final destination, plus each sibling of those nodes. This means that the number of comparisons will again be linear in the height of the tree (this time it will be 2 times the height of the tree).

To determine our worst case running time for both algorithms, all we need to do now is determine the height of the tree relative to the number of items the heap contains. To do this, let’s begin by approaching this in the opposite direction. We’ll start by fixing the height of the tree, then using that to identify how many items might be in the heap.

Suppose we have a heap that has height h. Because of the structure property, we know that all of the first h-1 levels must be completely full. A binary tree with h-1 levels, all completely full, will contain exactly 2^{h}-1 nodes (given by the geometric series 1+2+4+8+16+...+2^{h-1}). The final layer may then have between 1 and 2^h nodes in the tree. This means that the number of nodes in a tree of height h must be between 2^h and 2^{h+1}.

We can this use this observation to derive the height from the number of nodes. Suppose we have n nodes. We can identify an upper bound on the height of the tree by finding the smallest value of h such that n\leq 2^h. Solving for h we have h = \lceil log_2(n) \rceil. This means that the height of a heap is \Theta(\log(n)), where n is the number of items it contains.

Finally, we can see that because each of insert and extract are linear in terms of the height of the tree, their running times must be worst case \Theta(\log n).

2.4.4 Percolate Up and Down

Within the insert and extract algorithms there are two subroutines that are very helpful when manipulating heaps.

In insert we had a problem where a item was somewhere deep in the tree (near to a leaf), and it’s possible that it belongs somewhere shallower (near to the root) in order to restore the heap property. In this case we repeatedly swapped that potentially misplaced item with its parent until the heap property was restored. This procedure is given the name percolate up. The percolate up procedure can be started from any item in the tree. The idea is that if there is some item that we believe might be too deep (i.e. it might have a priority value smaller than its parent), then we can begin swapping it upward until it’s in the right position.

With extract we had the opposite problem. After moving the last item into the root’s position we had a item that was shallow that might need to go deeper in order to restore the heap property. In this case we repeated swapped that item with its smaller child until the heap property was restored. We call this procedure percolate down. If there is some item that we believe might be too shallow in the tree (i.e. it might have a priority value larger than one of its children’s), then we can begin swapping it downward until it’s in the right position.

With these subroutines, we can then rephrase the algorithm for insert as:

  1. Place the new item at the position dictated by the structure property
  2. Percolate up beginning from that item

and the algorithm or extract as:

  1. Save the value of the current root
  2. Move the item in the last index of the array to index 1 (overwriting and taking the place of the old root)
  3. Percolate down starting from index 1
  4. Return the saved value of the original root

Observe that both of these procedures’ worst case running times are linear in the height of the tree, and therefore \Theta(\log n).

2.4.5 Increase/Decrease Key

There are two more priority queue ADT operations that we have thus far ignored - increase and decrease key. The idea here is that if I want to change the priority value of an item, we might need to rearrange items to restore the heap property.

If we want to increase the priority value of an item then we will call increase key. Increasing the priority value will result a item potentially being too high in the heap (too near a root). This is because we previously knew that the item’s priority was at least that of its parent, and no more than those of its children. If we increase the priority value then it must still be at least that of its parent, but it might not be less than or equal to its children any longer. For this reason, we will need to percolate down on the item whose priority changed.

If we want to decrease the priority value of an item then we will call decrease key. This has the opposite effect. It could now be that the item is too low in the tree because it’s priority may have fallen below that of its parent. Therefore we want to percolate up on that item.

3 Max Heaps

Thus far our entire discussion has focused on heaps where the minimum priority value is considered the most important. This means that the heap property insures that each item’s priority is not more than its children’s, and that the root holds the minimum priority value. When we arrange elements in this way we call the data structure a min heap.

All of our discussion is equally valid if we reverse all of our inequalities. We could have defined our heap such that the largest priority value is considered most important, and therefore would be stored at the root. Such a heap is called a max heap. Max heaps are exactly the same as min heaps except the they must enforce the max heap property, which states that the priority each item in the heap must be greater than or equal to its children’s.

Be advised! The increase/decrease key operations in a max heap cause percolation to happen in the opposite direction compared to a min heap.

4 Floyd’s Build Heap Method

Suppose we have a collection of items, and we want to create a new heap containing all of those items. We could certainly do this by simply adding all of the items into the heap one-by-one. If there are n items to insert, and each insert operation in a heap requires \log n time, the running time of this process is \Theta(n \log n). It turns out there is a way we can build a heap containing a set of elements in linear time! This algorithm is called Floyd’s Build Heap Method.

Let’s start by describing the algorithm, and then we’ll evaluated the running time.

Here’s how the algorithm operates:

  1. Create an array of length n+1.
  2. Add all the items into the array in any arbitrary order from indices 1 to n.
  3. For each index in the array, starting from index n and going down to index 1, percolate down starting with that item.

At first this might look no different from the naive insert into the heap one at a time algorithm because we’re still doing a percolation per item in the heap. There is one very important observation about a binary tree that makes Floyd’s method more efficient, though. That is that binary trees are much bigger on the bottom compared to the top. In a completely full heap for example (i.e. one where every level is completely full), half of the nodes are leaves, one quarter of the nodes are in the second-from-last level, one eighth of the nodes are in the third-from-last level, and so on. By working from back to front in the array, and percolating down, we ensure that the majority of items (the leaves) have less distance to travel when percolating, because they’re already close to the bottom.

Now let’s do a more formal analysis of the running time. Because the first \frac{n}{2} nodes are already leaves, percolating down requires 0 comparisons. For the next \frac{n}{4} nodes, each must participate in 2 comparisons each in the worst case (each node must be compared with both of its children). For the next \frac{n}{8} nodes, each must participate in 4 comparisons in the worst case (each must be compared to its children, and then if we swap the children of the node we swapped with). The next \frac{n}{16} nodes, each must participate in 6 comparisons in the worst case. Continuing this process, the worst case number of comparisons is given by the series \frac{2n}{4}+\frac{4n}{8}+\frac{6n}{16}+\frac{8n}{32}+\frac{10n}{64}+..., where we have one term per level of the tree. Or expressed using sigma notation \sum_{i=1}^{\log_2 n}\frac{2in}{2^{i+1}}.

Let’s now figure out what this sums to. Let’s being with some rearranging.

\sum_{i=1}^{\log_2 n}\frac{2in}{2^{i+1}} = \sum_{i=1}^{\log_2 n}n\frac{i}{2^i} = n \sum_{i=1}^{\log_2 n}\frac{i}{2^i}

It turns out that this will be easier to analyze if we consider this as an infinite series. So far we’ve expressed the running time as n\sum_{i=1}^{\log_2 n}\frac{i}{2^i}, and we can be certain that the following sum is an upper bound on the running time: n\sum_{i=1}^{\infty}\frac{i}{2^i}. We’re going to skip the calculus on this, but the series \sum_{i=1}^{\infty}\frac{i}{2^i} converges to 2, and so our running time is upper bounded by 2n, giving a worst case running time of O(n). Because we upper bounded our running time by swapping out a finite series for an infinite series we only have an upper bound at the moment. We can easily establish that the running time is also \Omega(n) because the first time in this summation is itself n. Therefore our final running time is \Theta(n).