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.

Priority queue interface

See also: Abstract Data Types

Priority queue implementations:

• 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
• process of dating
• as information is processed, removing, re-evaluating, reinserting samples into a queue

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