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.




prio_queue = cluster [P, T: type] is new, empty, push, pop 
             where P has lt: proctype (P,P) returns (bool)
 
    item = struct[prio: P, val: T]
    rep = array[item]
 
    new = proc () returns (cvt)
        return (rep$create(0))
    end new 
 
    empty = proc (pq: cvt) returns (bool)
        return (rep$empty(pq))
    end empty
 
    parent = proc (k: int) returns (int)
        return ((k-1)/2)
    end parent
 
    left = proc (k: int) returns (int)
        return (2*k + 1)
    end left
 
    right = proc (k: int) returns (int)
        return (2*k + 2)
    end right
 
    swap = proc (pq: rep, a: int, b: int)
        temp: item := pq[a]
        pq[a] := pq[b]
        pq[b] := temp
    end swap 
 
    min_heapify = proc (pq: rep, k: int)
        l: int := left(k)
        r: int := right(k)
 
        smallest: int := k
        if l < rep$size(pq) cand pq[l].prio < pq[smallest].prio then
            smallest := l
        end
        if r < rep$size(pq) cand pq[r].prio < pq[smallest].prio then
            smallest := r 
        end
        if smallest ~= k then
            swap(pq, k, smallest)
            min_heapify(pq, smallest)
        end
    end min_heapify
 
    push = proc (pq: cvt, prio: P, val: T)
        rep$addh(pq, item${prio: prio, val: val})
 
        i: int := rep$high(pq)
        while i ~= 0 cand pq[i].prio < pq[parent(i)].prio do
            swap(pq, i, parent(i))
            i := parent(i)
        end
    end push
 
    pop = proc (pq: cvt) returns (P, T) signals (empty)
        if empty(up(pq)) then signal empty end
        if rep$size(pq) = 1 then
            i: item := rep$remh(pq)
            return (i.prio, i.val)
        end
 
        root: item := pq[0]
        pq[0] := rep$remh(pq)
        min_heapify(pq, 0)
        return (root.prio, root.val)
    end pop
end prio_queue
 
start_up = proc ()
    % use ints for priority and strings for data
    prioq = prio_queue[int,string] 
 
    % make the priority queue
    pq: prioq := prioq$new()
 
    % add some tasks 
    prioq$push(pq, 3, "Clear drains")
    prioq$push(pq, 4, "Feed cat")
    prioq$push(pq, 5, "Make tea")
    prioq$push(pq, 1, "Solve RC tasks")
    prioq$push(pq, 2, "Tax return")
 
    % print them all out in order
    po: stream := stream$primary_output()
    while ~prioq$empty(pq) do
        prio: int task: string
        prio, task := prioq$pop(pq)
        stream$putl(po, int$unparse(prio) || ": " || task)
    end
end start_up