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.