## Priority Queue

**priority Q**

NB. Do not confuse thepriority queue with the (non-priority) queue. |

The operations on a *Priority Queue* are:

- create an empty Priority Queue,
- insert an element having a certain priority to the Priority Queue,
- remove that element having the highest priority.

### Heap

The children, if they exist, of the element at `i' are at:

- left(i) = 2*i
- right(i) = 2*i + 1

a[i..j], where i>=1, is a *heap* iff
every element is no smaller than its children, if any.
Note that if a[1..j] is a heap,
a[1] must hold the largest value in a[ ].

Note, there is a similar definition for a heap with the smallest value at the top. It is also possible to use a[0..j-1] as the heap, but the definitions of left and right must be changed [-Exercise].

### Insertion

If a[1..i-1] is already a heap,
a new element could be placed at a[i] except that
it *might* violate the heap property,
i.e. it might be greater than its parent,
assuming that i>=2.
The parent is at position floor(i/2).
If the parent, p, is smaller than the new element,
then p can be moved down to a[i]
and the new element placed at p's old position.
The new element is larger than p (which used to be larger
than its children).
The only possible problem is that the new element *might* still be
larger than its *new* parent, if that exists.
No matter, work *up* the "tree" moving small parents down,
until either the top, a[1],
is reached or until a parent no smaller than the new element is found
and the new element can be placed.

function upHeap( child ) // PRE: a[1..child-1] is a Heap // POST: a[1..child] is a Heap { var newElt = a[child]; var parent = Math.floor(child/2); while( parent >= 1) // child has a parent { // INV: a[child .. ] is a Heap if( a[parent] < newElt ) { a[child] = a[parent]; // move parent down child = parent; parent = Math.floor(child/2); } else break; } // ASSERT: child == 1 || newElt <= a[parent] a[child] = newElt; }//upHeap // to insert: N++; a[N] = some new value; upHeap(N);

### Remove Highest Priority Element

The highest priority element is a[1], and can be returned,
but this leaves a hole at position 1.
The hole is filled by moving a[n] to a[1] and decreasing n.
This may violate the heap property,
in fact it is likely to do so because elements near the "bottom"
tend to be of low priority.
The solution is to move the element *down* the heap
until it is no smaller than its children, if any.

function downHeap( parent ) // PRE: a[parent+1..N] is a Heap, and parent >= 1 // POST: a[parent ..N] is a Heap { var newElt = a[parent]; var child = 2*parent; // left(parent) while( child <= N ) // parent has a child { // INV: a[1 .. parent] is a Heap if( child < N ) // has 2 children if( a[child+1] > a[child] ) child++; // right child is bigger if( newElt < a[child] ) { a[parent] = a[child]; parent = child; child = 2*parent; } else break; } // ASSERT: child > N || newElt >= a[child] a[parent] = newElt; }//downHeap // to remove highest priority element highest = a[1]; a[1] = a[N]; N--; downHeap(1)

### Demonstration

The HTML FORM below allows a Priority Queue to be manipulated.
You can create an empty Priority Queue,
add element(s), and
remove the element with the highest priority.
*Experiment!*

© L . A l l i s o n |

Elements to be inserted into the priority queue
should be put in the `add' window, then use the add button.
The output windows, `o/p', show the contents of the priority queue
(a) as a linear array and
(b) as a notional tree structure
with the root at the *left*.
When the highest priority element is selected and removed - `get top' -
the old and new contents of the array are also shown.

### Complexity

#### Time

The *height* of a heap of n elements is ~log_{2}(n),
and the maximum time for insertion and for removing the highest
priority item is O(log(n)).

#### Space

The heap operations take O(1)-space.