How to resolve the algorithm Priority queue step by step in the CLU programming language
How to resolve the algorithm Priority queue step by step in the CLU programming language
Table of Contents
Problem Statement
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.
Create a priority queue. The queue must support at least two operations:
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:
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.
Let's start with the solution:
Step by Step solution about How to resolve the algorithm Priority queue step by step in the CLU programming language
Source code in the clu programming language
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
You may also check:How to resolve the algorithm Command-line arguments step by step in the Euphoria programming language
You may also check:How to resolve the algorithm Loops/For with a specified step step by step in the Logo programming language
You may also check:How to resolve the algorithm Empty string step by step in the Visual Basic programming language
You may also check:How to resolve the algorithm Make directory path step by step in the Kotlin programming language
You may also check:How to resolve the algorithm Gotchas step by step in the Quackery programming language