PriorityQueue

containers.PriorityQueue( of T ) hands back its smallest element first, whatever order the elements went in. Use it when the next item to handle is the most urgent one, not the oldest.

#import "std/containers"

'' A PriorityQueue hands back its smallest element first.
dim deadlines as containers.PriorityQueue( of int32 )
dim days( 0 to 4 ) as int32 = { 14, 3, 30, 7, 3 }
for i as int32 = 0 to 4
    deadlines.Push( days( i ) )
next
print "soonest:"; deadlines.Peek( )
do until deadlines.IsEmpty( )
    print deadlines.Pop( );
loop
print

'' Any other order needs a comparer: does a leave before b?
type Bigger as function( byref a as int32, byref b as int32 ) as boolean
dim biggest as Bigger = function( byref a as int32, _
                                  byref b as int32 ) as boolean
    return a > b
end function

dim bids as containers.PriorityQueueBy( of int32, Bigger ) = _
    containers.PriorityQueueBy( of int32, Bigger )( biggest )
bids.Push( 120 ) : bids.Push( 450 ) : bids.Push( 300 )
print "top bid:"; bids.Pop( ); ", then"; bids.Pop( )

Output

soonest: 3
 3 3 7 14 30
top bid: 450, then 300

Push and Pop cost O(log n); Peek looks at the next element without removing it. Equal elements, like the two 3s, may leave in either order.

For any order other than smallest first, use containers.PriorityQueueBy( of T, TLess ) and give it a comparer when you construct it. less( a, b ) returns true when a must leave before b — the question a SortBy comparer answers. The second type argument is the comparer's type: the example names a procedure-pointer type, Bigger, for a plain lambda. A capturing lambda's type is written typeof( name ).

for each over a priority queue walks its internal order, which is not priority order. Take elements with Pop, or call ToSortedArray( ) for a sorted copy.

Activities

1. Loop over deadlines with for each before popping, and compare the order with the popped one.
2. Push records of a type with a priority field, ordered by a comparer.