A priority queue is somewhat similar to a queue, with an important distinction: each item is added to a priority queue with a priority level, and will be later removed from the queue with the highest priority element first. That is, the items are (conceptually) stored in the queue in priority order instead of in insertion order.



Task

Create a priority queue.   The queue must support at least two operations:

   Insertion.   An element is added to the queue with a priority (a numeric value).
   Top item removal.   Deletes the element or one of the elements with the current top priority and return it.


Optionally, other operations may be defined, such as peeking (find what current top priority/top element is), merging (combining two priority queues into one), etc.



To test your implementation, insert a number of elements into the queue, each with some random priority.

Then dequeue them sequentially; now the elements should be sorted by priority.

You can use the following task/priority items as input data:

        Priority         Task
       ══════════   ════════════════
           3         Clear drains
           4         Feed cat
           5         Make tea
           1         Solve RC tasks
           2         Tax return



The implementation should try to be efficient.   A typical implementation has   O(log n)   insertion and extraction time,   where   n   is the number of items in the queue.

You may choose to impose certain limits such as small range of allowed priority levels, limited capacity, etc.   If so, discuss the reasons behind it.




( ***** priotity queue ***** )
 
  [ stack ]                      is heap.pq     (     --> s   )
 
  [ stack ]                      is comp.pq     (     --> s   )
 
  [ unpack
    comp.pq put heap.pq put ]    is pq->stacks  (   p -->     )
 
  [ heap.pq take comp.pq take
    2 pack ]                     is stacks->pq  (     --> p   )
 
  [ heap.pq share swap peek ]    is heapeek     (   n --> x   )
 
  [ heap.pq take
    swap poke heap.pq put ]      is heapoke     ( n x -->     )
 
  [ 1 - 1 >> ]                   is parent      (   n --> n   )
 
  [ 0 > ]                        is has-parent  (   n --> b   )
 
  [ 1 << 1+ ]                    is child       (   n --> n   )
 
  [ child heap.pq share size < ] is has-child   (   n --> b   )
 
  [ 1+ ]                         is sibling     (   n --> n   )
 
  [ sibling
    heap.pq share size < ]       is has-sibling (   n --> b   )
 
  [ comp.pq share do ]           is compare     ( x x --> b   )
 
  [ 0 peek size ]                is pqsize      (   p --> n   )
 
  [ swap pq->stacks
    heap.pq take tuck size
    rot 0 join heap.pq put
    [ dup has-parent while
      dup parent
      rot over heapeek
      2dup compare iff
        [ 2swap unrot heapoke ]
        again
      rot 2drop swap ]
    heapoke
    stacks->pq ]                 is topq        ( p x --> p   )
 
  [ dup heapeek swap
    [ dup has-child while
      dup child
      dup has-sibling if
        [ dup sibling heapeek
          over heapeek
          compare if sibling ]
      dip over dup heapeek
      rot dip dup compare iff
        [ rot heapoke ] again
      2drop ]
    heapoke ]                    is heapify.pq  (   n -->     )
 
  [ dup pqsize 0 = if
      [ $ "Unexpectedly empty priority queue."
        fail ]
    pq->stacks heap.pq share
    behead
    over [] = iff
      [ swap heap.pq replace ]
    else
      [ swap -1 split
        swap join heap.pq put
        0 heapify.pq ]
    stacks->pq swap ]            is frompq      (   p --> p x )
 
  [ ]'[ 2 pack pq->stacks
    heap.pq share
    size 1 >> times
      [ i heapify.pq ]
    stacks->pq ]                 is pqwith      (   [ --> p   )
 
( ***** task ***** )
 
  [ 2 pack topq ]                is insert      ( p n $ --> p     )
 
  [ frompq unpack ]              is dequeue    (     p --> p n $ )
 
  [] pqwith [ 0 peek dip [ 0 peek ] < ]
 
  3 $ "Clear drains"   insert
  4 $ "Feed cat"       insert
  5 $ "Make tea"       insert
  1 $ "Solve RC tasks" insert
  2 $ "Tax return"     insert
 
  5 times 
    [ dequeue
      swap echo say ": "
      echo$ cr ]
  drop