52 lines
1.1 KiB
Plaintext
52 lines
1.1 KiB
Plaintext
sequence pq = {}
|
|
|
|
constant PRIORITY = 2
|
|
|
|
procedure pq_add(sequence item)
|
|
-- item is {object data, object priority}
|
|
integer n = length(pq)+1,
|
|
m = floor(n/2)
|
|
pq &= 0
|
|
-- append at end, then up heap
|
|
while m>0 and item[PRIORITY]<pq[m][PRIORITY] do
|
|
pq[n] = pq[m]
|
|
n = m
|
|
m = floor(m/2)
|
|
end while
|
|
pq[n] = item
|
|
end procedure
|
|
|
|
function pq_pop()
|
|
sequence result = pq[1]
|
|
|
|
integer qn = length(pq),
|
|
n = 1,
|
|
m = 2
|
|
while m<qn do
|
|
if m+1<qn and pq[m][PRIORITY]>pq[m+1][PRIORITY] then
|
|
m += 1
|
|
end if
|
|
if pq[qn][PRIORITY]<=pq[m][PRIORITY] then exit end if
|
|
pq[n] = pq[m]
|
|
n = m
|
|
m = m * 2
|
|
end while
|
|
pq[n] = pq[qn]
|
|
pq = pq[1..$-1]
|
|
return result
|
|
end function
|
|
|
|
constant set = shuffle({{"Clear drains", 3},
|
|
{"Feed cat", 4},
|
|
{"Make tea", 5},
|
|
{"Solve RC tasks", 1},
|
|
{"Tax return", 2}})
|
|
for i=1 to length(set) do
|
|
pq_add(set[i])
|
|
pq_add(set[rand(length(set))])
|
|
end for
|
|
|
|
while length(pq) do
|
|
?pq_pop()
|
|
end while
|