Priority Queues
A priority queue is essentially a list of items, each associated with a priority. In general, different items may have different priorities and we speak of one item having a higher priority than another. Given such a list we can determine which is the highest (or the lowest) priority item in the list. Items are inserted into a priority queue in any arbitrary order. However, items are withdrawn from a priority queue in order of their priorities starting with the highest priority item first.
¢ Often the items added to a queue have a priority associated with them: this priority determines the order in which they exit the queue - highest priority
items are removed first. We will store based on smalles item - it has the highest priority.
¢ Consider the software that manages a printer. In general, it is possible for users to submit documents for printing much more quickly than it is possible to
print them. A simple solution is to place the documents in a FIFO queue. In a sense this is fair, because the documents are printed on a first-come,
first-served basis.
¢ A user who has submitted a short document for printing will experience a long delay when much longer documents are already in the queue. An
alternative solution is to use a priority queue in which the shorter a document, the higher its priority. By printing the shortest documents first, we reduce
the level of
frustration experienced by the users.
¢ We could use a tree structure - which generally provides O(log n) performance for both insertion and deletion. Unfortunately, if the tree becomes
unbalanced, performance will degrade to O(n) in worst cases. This will probably not be acceptable when dealing with dangerous industrial processes,
nuclear reactors, flight control systems, and other life-critical systems.
¢ There is a structure that will provide guaranteed O(log n) performance for both insertion and deletion: it's called a heap.
¢ Heaps are based on the notion of a complete tree. A binary tree is called completely full if all its levels are filled with nodes. A binary tree is completely
full if it is of height h, and has 2h-1 nodes. Each level contains twice as many nodes as the preceding level.
¢ A binary tree is called complete if it has no gaps on any level. The last level may have some leaves missing on the right as shown below:
¢ A heap is a binary tree that satisfies two conditions:
Ø It is a complete tree
Ø The value in each node does not exceed any value in that node’s left and right subtrees.
¢ Heaps are allowed to have more than one data item with the same value, and values in the left subtree do not have to be ranked lower than values in the
right subtree.
¢ A heap can be used as a priority queue: the highest priority item is at the root and is trivially extracted. But if the root is deleted, we are left with two
sub-trees and we must efficiently re-create a single tree with the heap property. The value of the heap structure is that we can both extract the highest
priority item and insert a new item in O(log n) time.
¢ Removing an item from a priority queue is straightforward if the queue is represented by a binary heap. The next item to leave the queue will always be
the item at the top (root) of the heap.
¢ The shape of the heap is restored by removing the last leaf and placing it into the root. For the heap shown below, the position that must become empty
is the one occupied by the 87. This is placed in the vacant root position.
¢ This has violated the condition that the root must be greater than each of its children. To repair the order, we apply the “heapify” procedure in which the
value from the root moves down the heap until it falls into place.
¢ At each step down the value 87 is swapped with its smaller child.
¢ The heap property still has not been restored in the left subtree. So again interchange the 87 with the smaller of its children.
¢ We need to make at most h interchanges of a root of a subtree with one of its children to fully restore the heap property. Thus deletion from a heap is
O(log n).
¢ To add an item to a heap, we follow the reverse procedure. First we add the new node as the last leaf, and then apply a “reheap up” procedure to restore
the ordering property of the heap. “Reheap up” moves the new node up the tree, swapping places with its parent until the order is restored. For example,
adding the value 9 to the original heap would result in the following sequence of steps:
¢ Again, we require O(log n) exchanges.
¢ The properties of a complete tree lead to a very efficient storage mechanism using n sequential locations in an array.
¢ An important benefit of the array representation is that we can move around the tree, from parent to children or from child to parent, by simple arithmetic.
In general, if we number the nodes from 1 at the root then
Ø The left and right children of node i, if they are present, are at 2i and 2i + 1
Ø The parent of node i is at i/2 (truncated to an integer).
¢ Each consecutive level from left to right.
¢ In a Java implementation, it is convenient to leave items[0] unused. With this numbering of nodes, the children of the node items[i] can be found in items
[2*i] and items[2*i+1], and the parents of items[i] is in items [i/2].
