Online Help

A useful data structure that can be implemented in an object-oriented way with modules is the priority queue. A priority queue is a container data structure that admits the following operations:

Test for an empty priority queue

Insert a prioritized item into a priority queue

Return (non-destructively) the highest-priority item in the priority queue

Delete the highest priority item from a priority queue

The following table lists the methods of an object representation of priority queues.

This representation leads directly to the following Maple type, which can be used to identify priority queues.

`type/PriorityQueue` := '`module`( empty, top, insert,
delete )':

Priority queues can be implemented as Maple objects by writing a constructor for the objects.

PriorityQueue := proc( priority::procedure )
description "priority queue constructor";
local largs, lnargs;

lnargs := nargs;
if lnargs > 1 then
largs := [ args[ 2 .. -1 ] ];
else
largs := [];
end if;

module()
description "a priority queue";
export empty, top, insert,
size, delete, init;
local heap, nitems,
bubbleup, bubbledown;

nitems := 0;
heap := table();

bubbleup := proc( child::posint )
local parent;
parent := iquo( child, 2 );
if child > 1
and priority( heap[ child ] ) > priority( heap[
parent ] ) then
heap[ parent ], heap[ child ] := heap[ child ],
heap[ parent ];
procname( parent ); # recurse
end if;
end proc;

bubbledown := proc( parent::posint )
local child;
child := 2 * parent;
if child < nitems
and priority( heap[ 1 + child ] ) > priority(
heap[ child ] ) then
child := 1 + child;
end if;
if child <= nitems
and priority( heap[ parent ] ) < priority( heap[
child ] ) then
heap[ parent ], heap[ child ] := heap[ child ],
heap[ parent ];
procname( child ); # recurse (new parent)
end if;
end proc;

# Initialize the priority queue.
init := proc()
heap := table();
nitems := 0;
end proc;

# Test whether the priority queue is empty.
empty := () -> evalb( nitems < 1 );

# Return the number of items on the priority queue.
size := () -> nitems;

# Query the highest priority item.
top := proc()
if empty() then
error "priority queue is empty";
else
heap[ 1 ];
end if;
end proc;

# Delete the highest priority item from the
# priority queue.
delete := proc()
local val;
val := heap[ 1 ]; # val := top()
# move bottom to the top
heap[ 1 ] := heap[ nitems ];
# allow expression to be collected
heap[ nitems ] := evaln( heap[ nitems ] );
# decrement the bottom of heap counter
nitems := nitems - 1;
# heapify the array
bubbledown( 1 );
# return the value
val;
end proc;

# Insert an item into the priority queue.
insert := proc( v )
if nargs > 1 then
op( map( procname, [ args ] ) );
else
nitems := 1 + nitems;
heap[ nitems ] := v;
bubbleup( nitems );
end if;
end proc;

# Insert any initially specified items.
if lnargs > 1 then
insert( op( largs ) );
end if;
end module;
end proc:

The constructor takes a Maple procedure priority as its argument. For each expression placed on the queue, this procedure returns a numeric measure of its priority. Items on the queue are maintained in a prioritized order so that the highest priority items are removed first.

In this sample computation with a priority queue, use the Maple built-in procedure length as the priority of an expression. Here, the randomly generated expressions are all polynomials.

pq := PriorityQueue( x -> length( x ) );

$\mathrm{pq}≔\mathbf{module}\left(\right)...\mathbf{end\; module}$

for i from 1 to 10 do
pq:-insert( randpoly( x ) );
end do:

while not pq:-empty() do
pq:-delete();
end do;

$-10x^5+62x^4-82x^3+80x^2-44x+71$

$95x^5+11x^4-49x^3-47x^2+40x-81$

$91x^5+68x^4-10x^3+31x^2-51x+77$

$72x^5+37x^4-23x^3+87x^2+44x+29$

$98x^5-23x^4+10x^3-61x^2-8x-29$

$-17x^5-75x^4-10x^3-7x^2-40x+42$

$-50x^5+23x^4+75x^3-92x^2+6x+74$

$-7x^5+22x^4-55x^3-94x^2+87x-56$

$95x^5+x^4+x^3+55x^2-28x+16$

$-62x^4+97x^3-73x^2-4x-83$

Priority queues can be used to implement a heapsort algorithm.

HeapSort := proc( L::list(numeric) )
local pq, t, count;
pq := PriorityQueue( x -> -x, op( L ) );
t := array( 1 .. nops( L ) );
count := 0;
while not pq:-empty() do
count := 1 + count;
t[ count ] := pq:-delete();
end do;
ASSERT( count = nops( L ) );
[ seq( t[ count ], count = 1 .. nops( L ) ) ];
end proc:

r := rand(100):

L := [ seq( r(), i = 1 .. 20 ) ]:

HeapSort( L );

$\left[1\&comma;3\&comma;8\&comma;9\&comma;11\&comma;12\&comma;14\&comma;17\&comma;18\&comma;24\&comma;40\&comma;42\&comma;43\&comma;51\&comma;54\&comma;63\&comma;71\&comma;72\&comma;84\&comma;89\right]$

Note: The fully commented source code for the PriorityQueue constructor is available in the samples/ProgrammingGuide/PriorityQueue directory of the Maple installation.