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 ]).
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 */
90add_to_heap(heap(Q0,M),P,X,heap(Q1,N)) :-
91 meld(Q0,t(X,P,[]),Q1),
92 N is M+1.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).
115empty_heap(heap(nil,0)).Complexity: constant.
123singleton_heap(heap(t(X,P,[]), 1), P, X).
131get_from_heap(heap(t(X,P,Sub),M), P, X, heap(Q,N)) :-
132 pairing(Sub,Q),
133 N is M-1.
139heap_size(heap(_,N),N).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).
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).
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).
210min_of_heap(heap(t(X,P,_),_), P, X).
222min_of_heap(Q,Px,X,Py,Y) :-
223 get_from_heap(Q,Px,X,Q0),
224 min_of_heap(Q0,Py,Y).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)
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 or A* search and Kruskal's minimum-spanning-tree algorithm.
This module implements min-heaps, meaning that key-value items are retrieved in ascending order of key. In other words, the key determines the 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 values can be arbitrary Prolog terms, the keys determine the priority, so keys must be ordered by @=</2. This means that variables can be used as keys, but binding them in between heap operations may change the ordering. It also means that rational terms (cyclic trees), for which standard order is not well-defined, cannot be used as keys.
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).