Priority Queues

Notes

Skiena Chapter 3

Basics of priority queues

Priority queues are queues in which the elements are kept in a sorted order.

Scheduling jobs of relative importance is example where items should be maintained in the queue in order of importance.

Priority queues provide more flexibility than simple searching, because they allow for new elements to enter the system at arbitrary intervals.

The cost-effectiveness of inserting a new job into a queue, instead of constantly sorting and resorting and resorting again.

process of dating - example of application

• as information is processed, removing, re-evaluating, reinserting samples into a queue

Priority queue interface

See also: Abstract Data Types

Priority queue implementation details:

• insert(q,k) - given an item x with key k, insert into priority queue Q
• find-min(q) or find-max(q) - return a pointer to the item with the smallest/largest key value of all elements in priority queue
• delete-min(q) or delete-max(q) - remove item from priority queue whose key is min/max

Implementations

Priority queue complexity of operations, worst-case scenario?

Using an unsorted array:

Using a sorted array:

Using a balanced binary search tree:

Goodrich Chapter 9

priorities and priority queues

Example: air-traffic control center deciding which flights to clear for landing among many approaching the airport

Airport - example applications of stacks and queues

A priority queue is a collection of prioritized elements that allows arbitrary element insertion, and the removal of the element with the highest priority.

Most common for priorities to be expressed numerically, but any object can be used a a key so long as it supports comparison a < b

Mapping: keys to integers or real numbers

Priority queue ADT

The abstract data type supports removal of one item, the item with the highest priority, so this is essentially a queue with a modified remove method:

• P.add(k, v) - add an item with key k and value v into priority queue P
• P.min() - peek minimum item - return an item (k,v) representing the key and value of item in priority queue P with minimum key, but do not remove the item.
• P.remove_min() - remove minimum item - remove and return an item (k,v) that represents the key and value of minimum key in priority queue P

Implementation nodes

Several ways to concretely implement a priority queue. Two main ways:

• sorted
• unsorted

OOP principles also apply to our implementation:

• composition design pattern
• composition - one object consisting of multiple parts
• In this case, key and value
• Other examples of composition: x,y point and nearest neighboring point, String item and count of occurrences

Unsorted implementation

Unsorted implementation: fast add operation, slow min/remove min operation

For an unsorted array, can add anywhere so adding is O(1). Finding the minimum is an O(N) operation.

Unsorted Priority Queue class: extends Priority Queue class

Unsorted priority queue keeps track of things using a Positional List, which implements Doubly Linked List, which implements Linked List

Sorted implementation

Sorted has a slow add method and a fast minimum/remove minimum method.

For a sorted array, add method needs to find the appropriate place to add the item in the sorted list, but it always knows where the minimum item is.

The cost of inserting an item is worst-case O(N), since we have to at least traverse the array to reach the given node, and in the worst case that requires traversing N nodes. If we can randomly access nodes, however, we can find the minimum in O(log N) operations using a binary search.

Heap

The heap is a data structure offering some of the advantages of both a sorted and an unsorted array. (Trees have the advantage of sorting information hierarchically).

In this case, the heap uses the tree level to sort information by value.

Heap-Order Property: In a heap T, for every position p other than the root, the key stored at p is greater than or equal to the key stored at p's parent.

As a consequence, a minimum key is always stored at the root of T. The min or remove min method therefore has an easy time.

The heap must also satisfy an additional constraint: the heap must be complete.

Complete Binary Tree Property: A heap T with height h is a complete binary tree if levels 0, 1, 2, ..., h-1 of T have the maximum number of nodes possible (namely, level i has 2^i nodes, for 0 <= i <= (h-1)) and the remaining nodes at level h reside in the leftmost positions possible.

Basically, we fill in the levels, one level at a time, never skipping from one level to the next. This guarantees that the left and right subtrees of the root node cannot differ by more than 1 level.

Proof:

Heap height: a heap T with n entries has a height of floor(log(n)).

This relies on the fact that IF the tree T is complete, there can only be one incomplete level at a time, so levels 0 through h-1 of the tree T must be complete. The number of nodes this represents is

$n=1+2+4+...+2^{h-1}=2^{h}-1$

the number of nodes in level h is somewhere between 1 and $2^{h}$, so this means

$n\geq 2^{h}-1+1=2^{h}$

and

$n\leq 2^{h}-1+2^{h}=2^{h+1}-1$

Taking the log of both sides of these inequallities, we see:

$h\leq \log {(n)}$

$\log {(n+1)}-1\leq h$

These two, plus fact that h is integer, imply h = floor( log( n ) )

Inserting: Heap add and post-add

To add to a heap requires two actions:

• Add a new node to the tree
• Enforce the properties of a heap (arrangement by value)

The heap add action requires creating a new heap node to store the key value pair (k,v).

The compete binary property requires us to place the new node at the next available position on level h, or if the level h is filled, to place it in the left-most position of the next level.

The post-insert action requires us to enforce the properties of a heap through a process called up-bubbling.

If we have not inserted into an empty tree, we should compare the key of our new position p to p's parent, which we can denote q.

If key p >= key q, heap-order property satisfied, algorithm terminates.

If key p < key q, we need to restore heap-order property. We swap p and q.

Heap-order property is now satisfied for position p, but needs to be satisfied for position q. Keep applying the routine as you move up the tree until you stop.

The worst case is when a new node has been added that will become a new minimum for the heap: up-heap bubbling causing the new node to propagate all the way from its initial position, as a leaf node in the last level, to the root node. The worst-case cost is log(N).

Removing: Heap remove min and post-remove

The main method of the priority queue is a modification of the remove method of the queue ADT, the removeMin method. This removes the item at the root of the tree T. Once the root item is removed, however, the tree needs to be reconnected, which means removing is not as simple as an O(1) operation.

We need to ensure that the tree stays a complete binary tree. To do that, we copy the very last item in the tree into the root node, and ensure (in reverse order this time, from the root working toward the leaf nodes) that the heap-order property is satisfied for each position.

The post-removal algorithm to ensure heap-ordering is maintained is called down-heap bubbling. There are two cases for checking position p as we move down the tree and validate the values in the tree:

• Position p has no right child, so let c be th left child of p.
• Otherwise, p has both children, so let c be the child of p with minimal key.

If key of p <= key of c, heap order property is satisfied, algorithm terminates.

If key of p > key of c, we need to restore heap-order property, by swapping p and c.

When p has two children, we must consider the smaller of the two children.

Now that heap order is enforced for position p, we can move on to check position c. Continue swapping down T until no violation of the proeprty occurs. This is called down-heap bubbling.