Priority Queues - Maple Help
For the best experience, we recommend viewing online help using Google Chrome or Microsoft Edge.

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 ) );
 ${\mathrm{pq}}{≔}{\mathbf{module}}\left({}\right)\phantom{\rule[-0.0ex]{0.5em}{0.0ex}}{...}\phantom{\rule[-0.0ex]{0.5em}{0.0ex}}{\mathbf{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;
 ${-}{10}{}{{x}}^{{5}}{+}{62}{}{{x}}^{{4}}{-}{82}{}{{x}}^{{3}}{+}{80}{}{{x}}^{{2}}{-}{44}{}{x}{+}{71}$
 ${95}{}{{x}}^{{5}}{+}{11}{}{{x}}^{{4}}{-}{49}{}{{x}}^{{3}}{-}{47}{}{{x}}^{{2}}{+}{40}{}{x}{-}{81}$
 ${91}{}{{x}}^{{5}}{+}{68}{}{{x}}^{{4}}{-}{10}{}{{x}}^{{3}}{+}{31}{}{{x}}^{{2}}{-}{51}{}{x}{+}{77}$
 ${72}{}{{x}}^{{5}}{+}{37}{}{{x}}^{{4}}{-}{23}{}{{x}}^{{3}}{+}{87}{}{{x}}^{{2}}{+}{44}{}{x}{+}{29}$
 ${98}{}{{x}}^{{5}}{-}{23}{}{{x}}^{{4}}{+}{10}{}{{x}}^{{3}}{-}{61}{}{{x}}^{{2}}{-}{8}{}{x}{-}{29}$
 ${-}{17}{}{{x}}^{{5}}{-}{75}{}{{x}}^{{4}}{-}{10}{}{{x}}^{{3}}{-}{7}{}{{x}}^{{2}}{-}{40}{}{x}{+}{42}$
 ${-}{50}{}{{x}}^{{5}}{+}{23}{}{{x}}^{{4}}{+}{75}{}{{x}}^{{3}}{-}{92}{}{{x}}^{{2}}{+}{6}{}{x}{+}{74}$
 ${-}{7}{}{{x}}^{{5}}{+}{22}{}{{x}}^{{4}}{-}{55}{}{{x}}^{{3}}{-}{94}{}{{x}}^{{2}}{+}{87}{}{x}{-}{56}$
 ${95}{}{{x}}^{{5}}{+}{{x}}^{{4}}{+}{{x}}^{{3}}{+}{55}{}{{x}}^{{2}}{-}{28}{}{x}{+}{16}$
 ${-}{62}{}{{x}}^{{4}}{+}{97}{}{{x}}^{{3}}{-}{73}{}{{x}}^{{2}}{-}{4}{}{x}{-}{83}$ (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 );
 $\left[{1}{,}{3}{,}{8}{,}{9}{,}{11}{,}{12}{,}{14}{,}{17}{,}{18}{,}{24}{,}{40}{,}{42}{,}{43}{,}{51}{,}{54}{,}{63}{,}{71}{,}{72}{,}{84}{,}{89}\right]$ (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.