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, +Key, ?Value, -Heap 37 delete_from_heap/4, % +Heap0, -Key, +Value, -Heap 38 empty_heap/1, % +Heap 39 get_from_heap/4, % ?Heap0, ?Key, ?Value, -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, ?Key, ?Value 46 min_of_heap/5, % +Heap, ?Key1, ?Value1, 47 % ?Key2, ?Value2 48 singleton_heap/3 % ?Heap, ?Key, ?Value 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 such 56 * as best-first or A* search and Kruskal's minimum-spanning-tree algorithm. 57 * 58 * This module implements min-heaps, meaning that key-value items are retrieved in 59 * ascending order of key. In other words, the key determines the priority. It 60 * was designed to be compatible with the SICStus Prolog library module of the 61 * same name. merge_heaps/3 and singleton_heap/3 are SWI-specific extension. The 62 * portray_heap/1 predicate is not implemented. 63 * 64 * Although the values can be arbitrary Prolog terms, the keys determine the 65 * priority, so keys must be ordered by @=</2. This means that variables can be 66 * used as keys, but binding them in between heap operations may change the 67 * ordering. It also means that rational terms (cyclic trees), for which standard 68 * order is not well-defined, cannot be used as keys. 69 * 70 * The current version implements pairing heaps. These support insertion and 71 * merging both in constant time, deletion of the minimum in logarithmic amortized 72 * time (though delete-min, i.e., get_from_heap/3, takes linear time in the worst 73 * case). 74 * 75 * @author Lars Buitinck 76 */ 77 78/* 79 * Heaps are represented as heap(H,Size) terms, where H is a pairing heap and 80 * Size is an integer. A pairing heap is either nil or a term 81 * t(X,PrioX,Sub) where Sub is a list of pairing heaps t(Y,PrioY,Sub) s.t. 82 * PrioX @< PrioY. See predicate is_heap/2, below. 83 */ 84 85%! add_to_heap(+Heap0, +Key, ?Value, -Heap) is semidet. 86% 87% Adds Value with priority Key to Heap0, constructing a new 88% heap in Heap. 89 90add_to_heap(heap(Q0,M),P,X,heap(Q1,N)) :- 91 meld(Q0,t(X,P,[]),Q1), 92 N is M+1. 93 94%! delete_from_heap(+Heap0, -Key, +Value, -Heap) is semidet. 95% 96% Deletes Value from Heap0, leaving its priority in Key and the 97% resulting data structure in Heap. Fails if Value is not found in 98% Heap0. 99% 100% @bug This predicate is extremely inefficient and exists only for 101% SICStus compatibility. 102 103delete_from_heap(Q0,P,X,Q) :- 104 get_from_heap(Q0,P,X,Q), 105 !. 106delete_from_heap(Q0,Px,X,Q) :- 107 get_from_heap(Q0,Py,Y,Q1), 108 delete_from_heap(Q1,Px,X,Q2), 109 add_to_heap(Q2,Py,Y,Q). 110 111%! empty_heap(?Heap) is semidet. 112% 113% True if Heap is an empty heap. Complexity: constant. 114 115empty_heap(heap(nil,0)). 116 117%! singleton_heap(?Heap, ?Key, ?Value) is semidet. 118% 119% True if Heap is a heap with the single element Key-Value. 120% 121% Complexity: constant. 122 123singleton_heap(heap(t(X,P,[]), 1), P, X). 124 125%! get_from_heap(?Heap0, ?Key, ?Value, -Heap) is semidet. 126% 127% Retrieves the minimum-priority pair Key-Value from Heap0. 128% Heap is Heap0 with that pair removed. Complexity: logarithmic 129% (amortized), linear in the worst case. 130 131get_from_heap(heap(t(X,P,Sub),M), P, X, heap(Q,N)) :- 132 pairing(Sub,Q), 133 N is M-1. 134 135%! heap_size(+Heap, -Size:int) is det. 136% 137% Determines the number of elements in Heap. Complexity: constant. 138 139heap_size(heap(_,N),N). 140 141%! heap_to_list(+Heap, -List:list) is det. 142% 143% Constructs a list List of Key-Value terms, ordered by 144% (ascending) priority. Complexity: O(N log N). 145 146heap_to_list(Q,L) :- 147 to_list(Q,L). 148to_list(heap(nil,0),[]) :- !. 149to_list(Q0,[P-X|Xs]) :- 150 get_from_heap(Q0,P,X,Q), 151 heap_to_list(Q,Xs). 152 153%! is_heap(+X) is semidet. 154% 155% Returns true if X is a heap. Validates the consistency of the 156% entire heap. Complexity: linear. 157 158is_heap(V) :- 159 var(V), !, fail. 160is_heap(heap(Q,N)) :- 161 integer(N), 162 nonvar(Q), 163 ( Q == nil 164 -> N == 0 165 ; N > 0, 166 Q = t(_,MinP,Sub), 167 are_pairing_heaps(Sub, MinP) 168 ). 169 170% True iff 1st arg is a pairing heap with min key @=< 2nd arg, 171% where min key of nil is logically @> any term. 172is_pairing_heap(V, _) :- 173 var(V), 174 !, 175 fail. 176is_pairing_heap(nil, _). 177is_pairing_heap(t(_,P,Sub), MinP) :- 178 MinP @=< P, 179 are_pairing_heaps(Sub, P). 180 181% True iff 1st arg is a list of pairing heaps, each with min key @=< 2nd arg. 182are_pairing_heaps(V, _) :- 183 var(V), 184 !, 185 fail. 186are_pairing_heaps([], _). 187are_pairing_heaps([Q|Qs], MinP) :- 188 is_pairing_heap(Q, MinP), 189 are_pairing_heaps(Qs, MinP). 190 191%! list_to_heap(+List:list, -Heap) is det. 192% 193% If List is a list of Key-Value terms, constructs a heap 194% out of List. Complexity: linear. 195 196list_to_heap(Xs,Q) :- 197 empty_heap(Empty), 198 list_to_heap(Xs,Empty,Q). 199 200list_to_heap([],Q,Q). 201list_to_heap([P-X|Xs],Q0,Q) :- 202 add_to_heap(Q0,P,X,Q1), 203 list_to_heap(Xs,Q1,Q). 204 205%! min_of_heap(+Heap, ?Key, ?Value) is semidet. 206% 207% Unifies Value with the minimum-priority element of Heap and 208% Key with its priority value. Complexity: constant. 209 210min_of_heap(heap(t(X,P,_),_), P, X). 211 212%! min_of_heap(+Heap, ?Key1, ?Value1, ?Key2, ?Value2) is semidet. 213% 214% Gets the two minimum-priority elements from Heap. Complexity: logarithmic 215% (amortized). 216% 217% @bug This predicate is extremely inefficient and exists for compatibility 218% with earlier implementations of this library and SICStus 219% compatibility. It performs a linear amount of work in the worst case 220% that a following get_from_heap has to re-do. 221 222min_of_heap(Q,Px,X,Py,Y) :- 223 get_from_heap(Q,Px,X,Q0), 224 min_of_heap(Q0,Py,Y). 225 226%! merge_heaps(+Heap0, +Heap1, -Heap) is det. 227% 228% Merge the two heaps Heap0 and Heap1 in Heap. Complexity: constant. 229 230merge_heaps(heap(L,K),heap(R,M),heap(Q,N)) :- 231 meld(L,R,Q), 232 N is K+M. 233 234 235% Merge two pairing heaps according to the pairing heap definition. 236meld(nil,Q,Q) :- !. 237meld(Q,nil,Q) :- !. 238meld(L,R,Q) :- 239 L = t(X,Px,SubL), 240 R = t(Y,Py,SubR), 241 ( Px @< Py 242 -> Q = t(X,Px,[R|SubL]) 243 ; Q = t(Y,Py,[L|SubR]) 244 ). 245 246% "Pair up" (recursively meld) a list of pairing heaps. 247pairing([], nil). 248pairing([Q], Q) :- !. 249pairing([Q0,Q1|Qs], Q) :- 250 meld(Q0, Q1, Q2), 251 pairing(Qs, Q3), 252 meld(Q2, Q3, Q)