YAP
7.1.0
heaps.yap
Go to the documentation of this file.
1
/**
2
* @file heaps.yap
3
* @author R.A.O'Keefe, included as an YAP library by Vitor Santos Costa, 1999.
4
* @date 29 November 1983
5
*
6
* @brief Implement heaps in Prolog.
7
*
8
*
9
*/
10
11
:- module(
heaps
,[
12
add_to_heap/4
,
% Heap x Key x Datum -> Heap
13
get_from_heap/4,
% Heap -> Key x Datum x Heap
14
empty_heap/1
,
% Heap
15
heap_size/2
,
% Heap -> Size
16
heap_to_list/2
,
% Heap -> List
17
list_to_heap/2
,
% List -> Heap
18
min_of_heap/3
,
% Heap -> Key x Datum
19
min_of_heap/5
% Heap -> (Key x Datum) x (Key x Datum)
20
]).
21
22
23
/** @defgroup heaps Heaps
24
@ingroup YAPLibrary
25
@{
26
27
A heap is a labelled binary tree where the key of each node is less than
28
or equal to the keys of its sons. The point of a heap is that we can
29
keep on adding new elements to the heap and we can keep on taking out
30
the minimum element. If there are N elements total, the total time is
31
O(NlgN). If you know all the elements in advance, you are better off
32
doing a merge-sort, but this file is for when you want to do say a
33
best-first search, and have no idea when you start how many elements
34
there will be, let alone what they are.
35
36
The following heap manipulation routines are available once included
37
with the `use_module(library(heaps))` command.
38
39
- add_to_heap/4
40
- empty_heap/1
41
- get_from_heap/4
42
- heap_size/2
43
- heap_to_list/2
44
- list_to_heap/2
45
- min_of_heap/3
46
- min_of_heap/5
47
48
49
A heap is a labelled binary tree where the key of each node is less
50
than or equal to the keys of its sons. The point of a heap is that
51
we can keep on adding new elements to the heap and we can keep on
52
taking out the minimum element. If there are N elements total, the
53
total time is O(NlgN). If you know all the elements in advance, you
54
are better off doing a merge-sort, but this file is for when you want
55
to do say a best-first search, and have no idea when you start how
56
many elements there will be, let alone what they are.
57
58
A heap is represented as a triple t(N, Free, Tree) where N is the
59
number of elements in the tree, Free is a list of integers which
60
specifies unused positions in the tree, and Tree is a tree made of
61
t terms for empty subtrees and
62
t(Key,Datum,Lson,Rson) terms for the rest
63
The nodes of the tree are notionally numbered like this:
64
1
65
2 3
66
4 6 5 7
67
8 12 10 14 9 13 11 15
68
.. .. .. .. .. .. .. .. .. .. .. .. .. .. .. ..
69
The idea is that if the maximum number of elements that have been in
70
the heap so far is M, and the tree currently has K elements, the tree
71
is some subtreee of the tree of this form having exactly M elements,
72
and the Free list is a list of K-M integers saying which of the
73
positions in the M-element tree are currently unoccupied. This free
74
list is needed to ensure that the cost of passing N elements through
75
the heap is O(NlgM) instead of O(NlgN). For M say 100 and N say 10^4
76
this means a factor of two. The cost of the free list is slight.
77
The storage cost of a heap in a copying Prolog (which Dec-10 Prolog is
78
not) is 2K+3M words.
79
80
81
82
*/
83
84
/*
85
:- mode
86
add_to_heap(+, +, +, -),
87
add_to_heap(+, +, +, +, -),
88
add_to_heap(+, +, +, +, +, +, -, -),
89
sort2(+, +, +, +, -, -, -, -),
90
get_from_heap(+, ?, ?, -),
91
repair_heap(+, +, +, -),
92
heap_size(+, ?),
93
heap_to_list(+, -),
94
heap_tree_to_list(+, -),
95
heap_tree_to_list(+, +, -),
96
list_to_heap(+, -),
97
list_to_heap(+, +, +, -),
98
min_of_heap(+, ?, ?),
99
min_of_heap(+, ?, ?, ?, ?),
100
min_of_heap(+, +, ?, ?).
101
*/
102
103
104
%% @pred add_to_heap(OldHeap, Key, Datum, NewHeap)
105
%
106
% inserts the new Key-Datum pair into the heap. The insertion is
107
% not stable, that is, if you insert several pairs with the same
108
% Key it is not defined which of them will come out first, and it
109
% is possible for any of them to come out first depending on the
110
% history of the heap. If you need a stable heap, you could add
111
% a counter to the heap and include the counter at the time of
112
% insertion in the key. If the free list is empty, the tree will
113
% be grown, otherwise one of the empty slots will be re-used. (I
114
% use imperative programming language, but the heap code is as
115
% pure as the trees code, you can create any number of variants
116
% starting from the same heap, and they will share what common
117
% structure they can without interfering with each other.)
118
119
add_to_heap
(t(
M
,[],
OldTree
),
Key
,
Datum
, t(
N
,[],
NewTree
))
:-
add_to_heap,
120
N
is
M
+
1
,
121
add_to_heap(
N
,
Key
,
Datum
,
OldTree
,
NewTree
).
122
add_to_heap
(t(
M
,[
H
|
T
],
OldTree
),
Key
,
Datum
, t(
N
,
T
,
NewTree
))
:-
123
N
is
M
+
1
,
124
add_to_heap(
H
,
Key
,
Datum
,
OldTree
,
NewTree
).
125
126
127
add_to_heap(
1
,
Key
,
Datum
,
_
, t(
Key
,
Datum
,t,t))
:-
add_to_heap.
128
add_to_heap(
N
,
Key
,
Datum
, t(
K1
,
D1
,
L1
,
R1
), t(
K2
,
D2
,
L2
,
R2
))
:-
129
E
is
N
mod
2
,
130
M
is
N
//
2
,
131
% M > 0, % only called from list_to_heap/4,add_to_heap/4
132
sort2(
Key
,
Datum
,
K1
,
D1
,
K2
,
D2
,
K3
,
D3
),
133
add_to_heap(
E
,
M
,
K3
,
D3
,
L1
,
R1
,
L2
,
R2
).
134
135
136
add_to_heap(
0
,
N
,
Key
,
Datum
,
L1
,
R
,
L2
,
R
)
:-
add_to_heap,
137
add_to_heap(
N
,
Key
,
Datum
,
L1
,
L2
).
138
add_to_heap(
1
,
N
,
Key
,
Datum
,
L
,
R1
,
L
,
R2
)
:-
add_to_heap,
139
add_to_heap(
N
,
Key
,
Datum
,
R1
,
R2
).
140
141
142
sort2(
Key1
,
Datum1
,
Key2
,
Datum2
,
Key1
,
Datum1
,
Key2
,
Datum2
)
:-
143
Key1
@<
Key2
,
144
sort2.
145
sort2(
Key1
,
Datum1
,
Key2
,
Datum2
,
Key2
,
Datum2
,
Key1
,
Datum1
).
146
147
148
149
%% @pred @pred get_from_heap(+ _Heap_,- _key_,- _Datum_,- _Heap_)
150
%
151
% returns the Key-Datum pair in OldHeap with the smallest Key, and
152
% also a New Heap which is the Old Heap with that pair deleted.
153
% The easy part is picking off the smallest element. The hard part
154
% is repairing the heap structure. repair_heap/4 takes a pair of
155
% heaps and returns a new heap built from their elements, and the
156
% position number of the gap in the new tree. Note that repair_heap
157
% is *not* tail-recursive.
158
159
get_from_heap(t(
N
,
Free
,t(
Key
,
Datum
,
L
,
R
)),
Key
,
Datum
, t(
M
,[
Hole
|
Free
],
Tree
))
:-
160
M
is
N
-
1
,
161
repair_heap(
L
,
R
,
Tree
,
Hole
).
162
163
164
repair_heap(t(
K1
,
D1
,
L1
,
R1
), t(
K2
,
D2
,
L2
,
R2
), t(
K2
,
D2
,t(
K1
,
D1
,
L1
,
R1
),
R3
),
N
)
:-
165
K2
@<
K1
,
166
repair_heap,
167
repair_heap(
L2
,
R2
,
R3
,
M
),
168
N
is
2
*
M
+
1
.
169
repair_heap(t(
K1
,
D1
,
L1
,
R1
), t(
K2
,
D2
,
L2
,
R2
), t(
K1
,
D1
,
L3
,t(
K2
,
D2
,
L2
,
R2
)),
N
)
:-
repair_heap,
170
repair_heap(
L1
,
R1
,
L3
,
M
),
171
N
is
2
*
M
.
172
repair_heap(t(
K1
,
D1
,
L1
,
R1
), t, t(
K1
,
D1
,
L3
,t),
N
)
:-
repair_heap,
173
repair_heap(
L1
,
R1
,
L3
,
M
),
174
N
is
2
*
M
.
175
repair_heap(t, t(
K2
,
D2
,
L2
,
R2
), t(
K2
,
D2
,t,
R3
),
N
)
:-
repair_heap,
176
repair_heap(
L2
,
R2
,
R3
,
M
),
177
N
is
2
*
M
+
1
.
178
repair_heap(t, t, t,
1
)
:-
repair_heap.
179
180
181
182
%% @pred heap_size(+ _Heap_, - _Size_)
183
%
184
% reports the number of elements currently in the heap.
185
186
heap_size
(t(
Size
,
_
,
_
),
Size
).
187
188
189
190
%% @pred heap_to_list(+ _Heap_, - _List_)
191
%
192
% returns the current set of Key-Datum pairs in the Heap as a
193
% List, sorted into ascending order of Keys. This is included
194
% simply because I think every data structure foo ought to have
195
% a foo_to_list and list_to_foo relation (where, of course, it
196
% makes sense!) so that conversion between arbitrary data
197
% structures is as easy as possible. This predicate is basically
198
% just a merge sort, where we can exploit the fact that the tops
199
% of the subtrees are smaller than their descendants.
200
201
heap_to_list
(t(
_
,
_
,
Tree
),
List
)
:-
202
heap_tree_to_list(
Tree
,
List
).
203
204
205
heap_tree_to_list(t, [])
:-
heap_tree_to_list.
206
heap_tree_to_list(t(
Key
,
Datum
,
Lson
,
Rson
), [
Key
-
Datum
|
Merged
])
:-
207
heap_tree_to_list(
Lson
,
Llist
),
208
heap_tree_to_list(
Rson
,
Rlist
),
209
heap_tree_to_list(
Llist
,
Rlist
,
Merged
).
210
211
212
heap_tree_to_list([
H1
|
T1
], [
H2
|
T2
], [
H2
|
T3
])
:-
213
H2
@<
H1
,
214
heap_tree_to_list,
215
heap_tree_to_list([
H1
|
T1
],
T2
,
T3
).
216
heap_tree_to_list([
H1
|
T1
],
T2
, [
H1
|
T3
])
:-
heap_tree_to_list,
217
heap_tree_to_list(
T1
,
T2
,
T3
).
218
heap_tree_to_list([],
T
,
T
)
:-
heap_tree_to_list.
219
heap_tree_to_list(
T
, [],
T
).
220
221
222
223
%% @pred list_to_heap(+ _List_, - _Heap_)
224
%
225
% takes a list of Key-Datum pairs (such as keysort could be used to
226
% sort) and forms them into a heap. We could do that a wee bit
227
% faster by keysorting the list and building the tree directly, but
228
% this algorithm makes it obvious that the result is a heap, and
229
% could be adapted for use when the ordering predicate is not @<
230
% and hence keysort is inapplicable.
231
232
list_to_heap
(
List
,
Heap
)
:-
233
list_to_heap(
List
,
0
, t,
Heap
).
234
235
236
list_to_heap([],
N
,
Tree
, t(
N
,[],
Tree
))
:-
list_to_heap.
237
list_to_heap([
Key
-
Datum
|
Rest
],
M
,
OldTree
,
Heap
)
:-
238
N
is
M
+
1
,
239
add_to_heap(
N
,
Key
,
Datum
,
OldTree
,
MidTree
),
240
list_to_heap(
Rest
,
N
,
MidTree
,
Heap
).
241
242
243
244
%% @pred min_of_heap(Heap, Key, Datum)
245
%
246
% returns the Key-Datum pair at the top of the heap (which is of
247
% course the pair with the smallest Key), but does not remove it
248
% from the heap. It fails if the heap is empty.
249
250
251
/** @pred min_of_heap(+ _Heap_, - _Key_, - _Datum_)
252
253
254
Returns the Key-Datum pair at the top of the heap (which is of course
255
the pair with the smallest Key), but does not remove it from the heap.
256
*/
257
min_of_heap
(t(
_
,
_
,t(
Key
,
Datum
,
_
,
_
)),
Key
,
Datum
).
258
259
260
%% @pred @pred min_of_heap(+ _Heap_, - _Key1_, - _Datum1_, -_Key2_, - _Datum2_)
261
%
262
% returns the smallest (Key1) and second smallest (Key2) pairs in
263
% the heap, without deleting them. It fails if the heap does not
264
% have at least two elements.
265
min_of_heap(t(
_
,
_
,t(
Key1
,
Datum1
,
Lson
,
Rson
)),
Key1
,
Datum1
,
Key2
,
Datum2
)
:-
266
min_of_heap(
Lson
,
Rson
,
Key2
,
Datum2
).
267
268
269
min_of_heap(t(
Ka
,
_Da
,
_
,
_
), t(
Kb
,
Db
,
_
,
_
),
Kb
,
Db
)
:-
270
Kb
@<
Ka
,
min_of_heap.
271
min_of_heap(t(
Ka
,
Da
,
_
,
_
),
_
,
Ka
,
Da
).
272
min_of_heap(t, t(
Kb
,
Db
,
_
,
_
),
Kb
,
Db
).
273
274
/** @pred empty_heap(? _Heap_)
275
276
277
Succeeds if _Heap_ is an empty heap.
278
*/
279
empty_heap
(t(
0
,[],t)).
280
281
282
/** @} */
283
284
add_to_heap/4
add_to_heap(OldHeap, Key, Datum, NewHeap)
empty_heap/1
empty_heap(? Heap)
heap_size/2
heap_size(+ Heap, - Size)
heap_to_list/2
heap_to_list(+ Heap, - List)
list_to_heap/2
list_to_heap(+ List, - Heap)
min_of_heap/3
min_of_heap(Heap, Key, Datum)
library
heaps.yap
Generated by
1.9.3