Priority Queues

Many algorithms process items according to a particular order. For example, suppose you have to schedule a list of jobs given the deadline by which each job must be performed or else its importance relative to the other jobs. Scheduling jobs requires sorting them by time or importance, and then performing them in this sorted order.  

Priority queues provide extra flexibility over sorting, which is required because jobs often enter the system at arbitrary intervals. It is much more cost-effective to insert a new job into a priority queue than to re-sort everything. Also, the need to perform certain jobs may vanish before they are executed, meaning that they must be removed from the queue.

The basic priority queue supports three primary operations:

• Insert(Q,x): Given an item x with key k, insert it into the priority queue Q.
• Find-Minimum(Q) or Find-Maximum(Q): Return a pointer to the item whose key value is smaller (larger) than any other key in the priority queue Q.
• Delete-Minimum(Q) or Delete-Maximum(Q) - Remove the item from the priority queue Q whose key is minimum (maximum).

 
Figure: The maximum and minimum element in a binary search tree  

All three of these priority queue operations can be implemented in time by representing the heap with a binary search tree. Implementing the find-minimum operation requires knowing where the minimum element in the tree is. By definition, the smallest key must reside in the left subtree of the root, since all keys in the left subtree have values less than that of the root. Therefore, as shown in Figure , the minimum element must be the leftmost decendent of the root. Similarly, the maximum element must be the rightmost decendent of the root.  

Find-Maximum(x) 															 Find-Minimum(x)

		 while 												 		 while 

		 		     do x = right[x]										 				      do x = left[x]

		 return x														 		 return x

Repeatedly traversing left (or right) pointers until we hit a leaf takes time proportional to the height of the tree, or if the tree is balanced. The insert operation can be implemented exactly as binary tree insertion. Delete-Min can be implemented by finding the minimum element and then using standard binary tree deletion. It follows that each of the operations can be performed in time.

Priority queues are very useful data structures. Indeed, they are the hero of the war story described in Section . A complete set of priority queue implementations is presented in Section .