Example: Priority Queues - Maple Programming Help

Online Help

All Products    Maple    MapleSim


Home : Support : Online Help : Applications and Example Worksheets : Language and System : examples/PriorityQueues

Example: Priority Queues

Introduction

  

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

Design

  

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

Table 1: Priority Queue Methods

empty

Test for an empty priority queue

top

Return the highest priority item

insert

Insert a prioritized item

delete

Remove (and return) the highest priority item

  

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

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

Constructor Implementation

  

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 ) );

pqmodule...end module

(1)

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

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

10x5+62x482x3+80x244x+71

95x5+11x449x347x2+40x81

91x5+68x410x3+31x251x+77

72x5+37x423x3+87x2+44x+29

98x523x4+10x361x28x29

17x575x410x37x240x+42

50x5+23x4+75x392x2+6x+74

7x5+22x455x394x2+87x56

95x5+x4+x3+55x228x+16

62x4+97x373x24x83

(2)

Priority Queue Usage

  

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 );

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

(3)

 

  

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

Return to the Index of Example Worksheets.

See Also

examples/GenericGraphAlgorithms