Priority Queue

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

The operations on a Priority Queue are:

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

Heap

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

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!

add:
controls:
o/p:
o/p:
©
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 ~log2(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.

Notes