Priority queue: Difference between revisions

Content added Content deleted

Inline

@@ Line 1,808: / Line 1,808: @@
 user=> (into p [["Wax Car" 4]["Paint Fence" 1]["Sand Floor" 3]])
 {"Solve RC tasks" 1, "Paint Fence" 1, "Clear drains" 3, "Sand Floor" 3, "Wax Car" 4, "Feed cat" 4, "Make tea" 5}</lang>
+=={{header|CLU}}==
+This is a priority queue based on a binary heap. It uses CLU's dynamic
+array to store the data.
+There are no intrinsic limits on what kind of data can be used for the
+priority or the values themselves, except that the priority datatype
+must support the less-than operator.
+<lang clu>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</lang>
+{{out}}
+<pre>1: Solve RC tasks
+: Tax return
+: Clear drains
+: Feed cat
+: Make tea</pre>
 =={{header|CoffeeScript}}==