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 ]). 50 51/** <module> heaps/priority queues 52 * 53 * Heaps are data structures that return the entries inserted into them in an 54 * ordered fashion, based on a priority. This makes them the data structure of 55 * choice for implementing priority queues, a central element of algorithms 56 * such as best-first/A* search and Kruskal's minimum-spanning-tree algorithm. 57 * 58 * This module implements min-heaps, meaning that items are retrieved in 59 * ascending order of key/priority. It was designed to be compatible with 60 * the SICStus Prolog library module of the same name. merge_heaps/3 and 61 * singleton_heap/3 are SWI-specific extension. The portray_heap/1 predicate 62 * is not implemented. 63 * 64 * Although the data items can be arbitrary Prolog data, keys/priorities must 65 * be ordered by @=</2. Be careful when using variables as keys, since binding 66 * them in between heap operations may change the ordering. 67 * 68 * The current version implements pairing heaps. These support insertion and 69 * merging both in constant time, deletion of the minimum in logarithmic 70 * amortized time (though delete-min, i.e., get_from_heap/3, takes linear time 71 * in the worst case). 72 * 73 * @author Lars Buitinck 74 */ 75 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 */ 82 83%! add_to_heap(+Heap0, +Priority, ?Key, -Heap) is semidet. 84% 85% Adds Key with priority Priority to Heap0, constructing a new 86% heap in Heap. 87 88add_to_heap(heap(Q0,M),P,X,heap(Q1,N)) :- 89 meld(Q0,t(X,P,[]),Q1), 90 N is M+1. 91 92%! delete_from_heap(+Heap0, -Priority, +Key, -Heap) is semidet. 93% 94% Deletes Key from Heap0, leaving its priority in Priority and the 95% resulting data structure in Heap. Fails if Key is not found in 96% Heap0. 97% 98% @bug This predicate is extremely inefficient and exists only for 99% SICStus compatibility. 100 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). 108 109%! empty_heap(?Heap) is semidet. 110% 111% True if Heap is an empty heap. Complexity: constant. 112 113empty_heap(heap(nil,0)). 114 115%! singleton_heap(?Heap, ?Priority, ?Key) is semidet. 116% 117% True if Heap is a heap with the single element Priority-Key. 118% 119% Complexity: constant. 120 121singleton_heap(heap(t(X,P,[]), 1), P, X). 122 123%! get_from_heap(?Heap0, ?Priority, ?Key, -Heap) is semidet. 124% 125% Retrieves the minimum-priority pair Priority-Key from Heap0. 126% Heap is Heap0 with that pair removed. Complexity: logarithmic 127% (amortized), linear in the worst case. 128 129get_from_heap(heap(t(X,P,Sub),M), P, X, heap(Q,N)) :- 130 pairing(Sub,Q), 131 N is M-1. 132 133%! heap_size(+Heap, -Size:int) is det. 134% 135% Determines the number of elements in Heap. Complexity: constant. 136 137heap_size(heap(_,N),N). 138 139%! heap_to_list(+Heap, -List:list) is det. 140% 141% Constructs a list List of Priority-Element terms, ordered by 142% (ascending) priority. Complexity: $O(n \log n)$. 143 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). 150 151%! is_heap(+X) is semidet. 152% 153% Returns true if X is a heap. Validates the consistency of the 154% entire heap. Complexity: linear. 155 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). 188 189%! list_to_heap(+List:list, -Heap) is det. 190% 191% If List is a list of Priority-Element terms, constructs a heap 192% out of List. Complexity: linear. 193 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). 202 203%! min_of_heap(+Heap, ?Priority, ?Key) is semidet. 204% 205% Unifies Key with the minimum-priority element of Heap and 206% Priority with its priority value. Complexity: constant. 207 208min_of_heap(heap(t(X,P,_),_), P, X). 209 210%! min_of_heap(+Heap, ?Priority1, ?Key1, ?Priority2, ?Key2) is semidet. 211% 212% Gets the two minimum-priority elements from Heap. Complexity: logarithmic 213% (amortized). 214% 215% Do not use this predicate; it exists for compatibility with earlier 216% implementations of this library and the SICStus counterpart. It performs 217% a linear amount of work in the worst case that a following get_from_heap 218% has to re-do. 219 220min_of_heap(Q,Px,X,Py,Y) :- 221 get_from_heap(Q,Px,X,Q0), 222 min_of_heap(Q0,Py,Y). 223 224%! merge_heaps(+Heap0, +Heap1, -Heap) is det. 225% 226% Merge the two heaps Heap0 and Heap1 in Heap. Complexity: constant. 227 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)