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