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. All operations can be
performed in at most O(lg n) amortized time, except for delete_from_heap/4,
heap_to_list/2, is_heap/1 and list_to_heap/2.
(The actual time complexity of pairing heaps is complicated and not yet
determined conclusively; see, e.g. S. Pettie (2005), Towards a final
analysis of pairing heaps, Proc. FOCS'05.)
- - Lars Buitinck
- - The "decrease key" operation is not implemented.
- add_to_heap(+Heap0, +Priority, ?Key, -Heap) is semidet
- Adds Key with priority Priority to Heap0, constructing a new
heap in Heap.
- 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
- - This predicate is extremely inefficient and exists only for
- empty_heap(?Heap) is semidet
- True if Heap is an empty heap.
- singleton_heap(?Heap, ?Priority, ?Key) is semidet
- True if Heap is a heap with the single element Priority-Key.
- 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.
- heap_size(+Heap, -Size:int) is det
- Determines the number of elements in Heap.
- heap_to_list(+Heap, -List:list) is det
- Constructs a list List of Priority-Element terms, ordered by
- is_heap(+X) is semidet
- Returns true is X is a heap.
- - May return false positives.
- list_to_heap(+List:list, -Heap) is det
- If List is a list of Priority-Element terms, constructs a heap
out of List.
- min_of_heap(+Heap, ?Priority, ?Key) is semidet
- Unifies Key with the minimum-priority element of Heap and
Priority with its priority value.
- min_of_heap(+Heap, ?Priority1, ?Key1, ?Priority2, ?Key2) is semidet
- Gets the two minimum-priority elements from Heap.
- merge_heaps(+Heap0, +Heap1, -Heap) is det
- Merge the two heaps Heap0 and Heap1 in Heap.