- author
- Lars Buitinck
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).
- [semidet]add_to_heap(+Heap0,
+Priority, ?Key, -Heap)
- Adds Key with priority Priority to Heap0,
constructing a new heap in Heap.
- [semidet]delete_from_heap(+Heap0,
-Priority, +Key, -Heap)
- 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.
- [semidet]empty_heap(?Heap)
- True if Heap is an empty heap. Complexity: constant.
- [semidet]singleton_heap(?Heap,
?Priority, ?Key)
- True if Heap is a heap with the single element Priority-Key.
Complexity: constant.
- [semidet]get_from_heap(?Heap0,
?Priority, ?Key, -Heap)
- Retrieves the minimum-priority pair Priority-Key
from Heap0.
Heap is Heap0 with that pair removed. Complexity:
logarithmic (amortized), linear in the worst case.
- [det]heap_size(+Heap,
-Size:int)
- Determines the number of elements in Heap. Complexity:
constant.
- [det]heap_to_list(+Heap,
-List:list)
- Constructs a list List of Priority-Element terms, ordered by
(ascending) priority. Complexity: $O(n
\log n)$.
- [semidet]is_heap(+X)
- Returns true if X is a heap. Validates the consistency of the
entire heap. Complexity: linear.
- [det]list_to_heap(+List:list,
-Heap)
- If List is a list of Priority-Element terms, constructs a
heap out of List. Complexity: linear.
- [semidet]min_of_heap(+Heap,
?Priority, ?Key)
- Unifies Key with the minimum-priority element of Heap
and
Priority with its priority value. Complexity: constant.
- [semidet]min_of_heap(+Heap,
?Priority1, ?Key1, ?Priority2, ?Key2)
- 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.
- [det]merge_heaps(+Heap0,
+Heap1, -Heap)
- Merge the two heaps Heap0 and Heap1 in Heap.
Complexity: constant.