View source with raw comments or as raw
    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          ]).

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).

author
- Lars Buitinck /
   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 */
 add_to_heap(+Heap0, +Priority, ?Key, -Heap) is semidet
Adds Key with priority Priority to Heap0, constructing a new heap in Heap.
   88add_to_heap(heap(Q0,M),P,X,heap(Q1,N)) :-
   89    meld(Q0,t(X,P,[]),Q1),
   90    N is M+1.
 delete_from_heap(+Heap0, -Priority, +Key, -Heap) is semidet
Deletes Key from Heap0, leaving its priority in Priority and the resulting data structure in Heap. Fails if Key is not found in Heap0.
bug
- This predicate is extremely inefficient and exists only for SICStus compatibility.
  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).
 empty_heap(?Heap) is semidet
True if Heap is an empty heap. Complexity: constant.
  113empty_heap(heap(nil,0)).
 singleton_heap(?Heap, ?Priority, ?Key) is semidet
True if Heap is a heap with the single element Priority-Key.

Complexity: constant.

  121singleton_heap(heap(t(X,P,[]), 1), P, X).
 get_from_heap(?Heap0, ?Priority, ?Key, -Heap) is semidet
Retrieves the minimum-priority pair Priority-Key from Heap0. Heap is Heap0 with that pair removed. Complexity: logarithmic (amortized), linear in the worst case.
  129get_from_heap(heap(t(X,P,Sub),M), P, X, heap(Q,N)) :-
  130    pairing(Sub,Q),
  131    N is M-1.
 heap_size(+Heap, -Size:int) is det
Determines the number of elements in Heap. Complexity: constant.
  137heap_size(heap(_,N),N).
 heap_to_list(+Heap, -List:list) is det
Constructs a list List of Priority-Element terms, ordered by (ascending) priority. Complexity: $O(n \log 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).
 is_heap(+X) is semidet
Returns true if X is a heap. Validates the consistency of the entire heap. Complexity: linear.
  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).
 list_to_heap(+List:list, -Heap) is det
If List is a list of Priority-Element terms, constructs a heap out of List. Complexity: linear.
  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).
 min_of_heap(+Heap, ?Priority, ?Key) is semidet
Unifies Key with the minimum-priority element of Heap and Priority with its priority value. Complexity: constant.
  208min_of_heap(heap(t(X,P,_),_), P, X).
 min_of_heap(+Heap, ?Priority1, ?Key1, ?Priority2, ?Key2) is semidet
Gets the two minimum-priority elements from Heap. Complexity: logarithmic (amortized).

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).
 merge_heaps(+Heap0, +Heap1, -Heap) is det
Merge the two heaps Heap0 and Heap1 in Heap. Complexity: constant.
  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)