|
NB. Do not confuse the priority 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!
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
- The Heap data-structures is central to
Heap Sort.
- Also see the (non-priority)
[Queue] ADT.
Do not confuse a queue with a priority queue;
the former can be thought of as a special case of the latter
in which priority is time of arrival, but a queue
is far simpler to implement than a priority queue.
|
|