1/* Part of SWI-Prolog 2 3 Author: Lars Buitinck 4 E-mail: larsmans@gmail.com 5 WWW: http://www.swi-prolog.org 6 Copyright (c) 2006-2015, Lars Buitinck 7 All rights reserved. 8 9 Redistribution and use in source and binary forms, with or without 10 modification, are permitted provided that the following conditions 11 are met: 12 13 1. Redistributions of source code must retain the above copyright 14 notice, this list of conditions and the following disclaimer. 15 16 2. Redistributions in binary form must reproduce the above copyright 17 notice, this list of conditions and the following disclaimer in 18 the documentation and/or other materials provided with the 19 distribution. 20 21 THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS 22 "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT 23 LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS 24 FOR A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE 25 COPYRIGHT OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, 26 INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, 27 BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; 28 LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER 29 CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT 30 LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN 31 ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE 32 POSSIBILITY OF SUCH DAMAGE. 33*/ 34 35:- module(heaps, 36 [ add_to_heap/4, % +Heap0, +Priority, ?Key, -Heap 37 delete_from_heap/4, % +Heap0, -Priority, +Key, -Heap 38 empty_heap/1, % +Heap 39 get_from_heap/4, % ?Heap0, ?Priority, ?Key, -Heap 40 heap_size/2, % +Heap, -Size:int 41 heap_to_list/2, % +Heap, -List:list 42 is_heap/1, % +Term 43 list_to_heap/2, % +List:list, -Heap 44 merge_heaps/3, % +Heap0, +Heap1, -Heap 45 min_of_heap/3, % +Heap, ?Priority, ?Key 46 min_of_heap/5, % +Heap, ?Priority1, ?Key1, 47 % ?Priority2, ?Key2 48 singleton_heap/3 % ?Heap, ?Priority, ?Key 49 ]).
76/*
77 * Heaps are represented as heap(H,Size) terms, where H is a pairing heap and
78 * Size is an integer. A pairing heap is either nil or a term
79 * t(X,PrioX,Sub) where Sub is a list of pairing heaps t(Y,PrioY,Sub) s.t.
80 * PrioX @< PrioY. See predicate is_heap/2, below.
81 */
88add_to_heap(heap(Q0,M),P,X,heap(Q1,N)) :-
89 meld(Q0,t(X,P,[]),Q1),
90 N is M+1.101delete_from_heap(Q0,P,X,Q) :- 102 get_from_heap(Q0,P,X,Q), 103 !. 104delete_from_heap(Q0,Px,X,Q) :- 105 get_from_heap(Q0,Py,Y,Q1), 106 delete_from_heap(Q1,Px,X,Q2), 107 add_to_heap(Q2,Py,Y,Q).
113empty_heap(heap(nil,0)).Complexity: constant.
121singleton_heap(heap(t(X,P,[]), 1), P, X).
129get_from_heap(heap(t(X,P,Sub),M), P, X, heap(Q,N)) :-
130 pairing(Sub,Q),
131 N is M-1.
137heap_size(heap(_,N),N).144heap_to_list(Q,L) :- 145 to_list(Q,L). 146to_list(heap(nil,0),[]) :- !. 147to_list(Q0,[P-X|Xs]) :- 148 get_from_heap(Q0,P,X,Q), 149 heap_to_list(Q,Xs).
156is_heap(V) :- 157 var(V), !, fail. 158is_heap(heap(Q,N)) :- 159 integer(N), 160 nonvar(Q), 161 ( Q == nil 162 -> N == 0 163 ; N > 0, 164 Q = t(_,MinP,Sub), 165 are_pairing_heaps(Sub, MinP) 166 ). 167 168% True iff 1st arg is a pairing heap with min key @=< 2nd arg, 169% where min key of nil is logically @> any term. 170is_pairing_heap(V, _) :- 171 var(V), 172 !, 173 fail. 174is_pairing_heap(nil, _). 175is_pairing_heap(t(_,P,Sub), MinP) :- 176 MinP @=< P, 177 are_pairing_heaps(Sub, P). 178 179% True iff 1st arg is a list of pairing heaps, each with min key @=< 2nd arg. 180are_pairing_heaps(V, _) :- 181 var(V), 182 !, 183 fail. 184are_pairing_heaps([], _). 185are_pairing_heaps([Q|Qs], MinP) :- 186 is_pairing_heap(Q, MinP), 187 are_pairing_heaps(Qs, MinP).
194list_to_heap(Xs,Q) :- 195 empty_heap(Empty), 196 list_to_heap(Xs,Empty,Q). 197 198list_to_heap([],Q,Q). 199list_to_heap([P-X|Xs],Q0,Q) :- 200 add_to_heap(Q0,P,X,Q1), 201 list_to_heap(Xs,Q1,Q).
208min_of_heap(heap(t(X,P,_),_), P, X).Do not use this predicate; it exists for compatibility with earlier implementations of this library and the SICStus counterpart. It performs a linear amount of work in the worst case that a following get_from_heap has to re-do.
220min_of_heap(Q,Px,X,Py,Y) :-
221 get_from_heap(Q,Px,X,Q0),
222 min_of_heap(Q0,Py,Y).228merge_heaps(heap(L,K),heap(R,M),heap(Q,N)) :- 229 meld(L,R,Q), 230 N is K+M. 231 232 233% Merge two pairing heaps according to the pairing heap definition. 234meld(nil,Q,Q) :- !. 235meld(Q,nil,Q) :- !. 236meld(L,R,Q) :- 237 L = t(X,Px,SubL), 238 R = t(Y,Py,SubR), 239 ( Px @< Py 240 -> Q = t(X,Px,[R|SubL]) 241 ; Q = t(Y,Py,[L|SubR]) 242 ). 243 244% "Pair up" (recursively meld) a list of pairing heaps. 245pairing([], nil). 246pairing([Q], Q) :- !. 247pairing([Q0,Q1|Qs], Q) :- 248 meld(Q0, Q1, Q2), 249 pairing(Qs, Q3), 250 meld(Q2, Q3, Q)
heaps/priority queues
Heaps are data structures that return the entries inserted into them in an ordered fashion, based on a priority. This makes them the data structure of choice for implementing priority queues, a central element of algorithms such as best-first/A* search and Kruskal's minimum-spanning-tree algorithm.
This module implements min-heaps, meaning that items are retrieved in ascending order of key/priority. It was designed to be compatible with the SICStus Prolog library module of the same name. merge_heaps/3 and singleton_heap/3 are SWI-specific extension. The portray_heap/1 predicate is not implemented.
Although the data items can be arbitrary Prolog data, keys/priorities must be ordered by @=</2. Be careful when using variables as keys, since binding them in between heap operations may change the ordering.
The current version implements pairing heaps. These support insertion and merging both in constant time, deletion of the minimum in logarithmic amortized time (though delete-min, i.e., get_from_heap/3, takes linear time in the worst case).