% This LaTeX document was generated using the LaTeX backend of PlDoc,
% The SWI-Prolog documentation system



\section{library(heaps): heaps/priority queues}

\label{sec:heaps}

\begin{tags}
    \tag{author}
Lars Buitinck
\end{tags}

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. \predref{merge_heaps}{3} and
\predref{singleton_heap}{3} are SWI-specific extension. The \predref{portray_heap}{1} predicate
is not implemented.

Although the data items can be arbitrary Prolog data, keys/priorities must
be ordered by \predref{\Stle}{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., \predref{get_from_heap}{3}, takes linear time
in the worst case).\vspace{0.7cm}

\begin{description}
    \predicate[semidet]{add_to_heap}{4}{+Heap0, +Priority, ?Key, -Heap}
Adds \arg{Key} with priority \arg{Priority} to \arg{Heap0}, constructing a new
heap in \arg{Heap}.

    \predicate[semidet]{delete_from_heap}{4}{+Heap0, -Priority, +Key, -Heap}
Deletes \arg{Key} from \arg{Heap0}, leaving its priority in \arg{Priority} and the
resulting data structure in \arg{Heap}. Fails if \arg{Key} is not found in
\arg{Heap0}.

\begin{tags}
    \tag{bug}
This predicate is extremely inefficient and exists only for
SICStus compatibility.
\end{tags}

    \predicate[semidet]{empty_heap}{1}{?Heap}
True if \arg{Heap} is an empty heap. Complexity: constant.

    \predicate[semidet]{singleton_heap}{3}{?Heap, ?Priority, ?Key}
True if \arg{Heap} is a heap with the single element \arg{Priority}-\arg{Key}.

Complexity: constant.

    \predicate[semidet]{get_from_heap}{4}{?Heap0, ?Priority, ?Key, -Heap}
Retrieves the minimum-priority pair \arg{Priority}-\arg{Key} from \arg{Heap0}.
\arg{Heap} is \arg{Heap0} with that pair removed. Complexity: logarithmic
(amortized), linear in the worst case.

    \predicate[det]{heap_size}{2}{+Heap, -Size:int}
Determines the number of elements in \arg{Heap}. Complexity: constant.

    \predicate[det]{heap_to_list}{2}{+Heap, -List:list}
Constructs a list \arg{List} of Priority-Element terms, ordered by
(ascending) priority. Complexity: \$O(n \Sneg{}log n)\$.

    \predicate[semidet]{is_heap}{1}{+X}
Returns true if \arg{X} is a heap. Validates the consistency of the
entire heap. Complexity: linear.

    \predicate[det]{list_to_heap}{2}{+List:list, -Heap}
If \arg{List} is a list of Priority-Element terms, constructs a heap
out of \arg{List}. Complexity: linear.

    \predicate[semidet]{min_of_heap}{3}{+Heap, ?Priority, ?Key}
Unifies \arg{Key} with the minimum-priority element of \arg{Heap} and
\arg{Priority} with its priority value. Complexity: constant.

    \predicate[semidet]{min_of_heap}{5}{+Heap, ?Priority1, ?Key1, ?Priority2, ?Key2}
Gets the two minimum-priority elements from \arg{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.

    \predicate[det]{merge_heaps}{3}{+Heap0, +Heap1, -Heap}
Merge the two heaps \arg{Heap0} and \arg{Heap1} in \arg{Heap}. Complexity: constant.
\end{description}