1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
|
############################################################################
#
# File: pqueue.icn
#
# Subject: Procedures for manipulating priority queues
#
# Authors: William S. Evans and Gregg M. Townsend
#
# Date: May 3, 2001
#
############################################################################
#
# This file is in the public domain.
#
############################################################################
#
# These procedures manipulate priority queues.
#
# pq(L) returns a priority queue containing the elements
# in L. L is a list (or table or set) of pqelem
# records, each containing a data and priority field.
# If L is &null, pq() returns an empty priority queue.
#
# pqget(Q) returns and removes the highest priority element
# from Q. Q is a priority queue returned by pq().
#
# pqput(Q, e) adds element e (a pqelem record) to Q.
#
# pqgen(Q) generates the elements in Q in priority order.
#
# pqelem(d, p) constructs a record with data d and priority p.
#
############################################################################
#
# Priority queues are implemented as heaps. Heaps are
# implemented as lists in the usual fashion.
#
############################################################################
record pqelem (
data, # element's data
priority # element's priority
)
procedure pq(L) #: create priority queue
local Q, i, e
/L := list()
Q := list()
every e := !L do
put(Q, pqelem(e.data, numeric(e.priority) | runerr(102, e.priority)))
every i := *Q / 2 to 1 by -1 do
pq__down(Q, i)
return Q
end
procedure pqget(Q) #: remove first priority queue element
local e
e := get(Q) | fail
push(Q, pull(Q))
pq__down(Q, 1)
return e
end
procedure pqgen(Q) #: generate priority queue elements
local q, e
q := copy(Q)
while e := copy(pqget(q)) do
suspend e
end
procedure pqput(Q, e) #: insert priority queue element
put(Q, pqelem(e.data, numeric(e.priority) | runerr(102, e.priority)))
pq__up(Q, *Q)
return Q
end
# Procedures named with a "pq__" prefix are not
# intended for access outside this file.
procedure pq__down(Q, i)
local left, right, largest
left := i * 2
right := left + 1
if Q[left].priority > Q[i].priority then largest := left
else largest := i
if Q[right].priority > Q[largest].priority then largest := right
if largest ~= i then {
Q[i] :=: Q[largest]
pq__down(Q, largest)
}
return
end
procedure pq__up(Q, i)
local parent
parent := i / 2
if Q[i].priority > Q[parent].priority then {
Q[i] :=: Q[parent]
pq__up(Q, parent)
}
return
end
|
