Did you know ... Search Documentation:
heaps.pl -- heaps/priority queues
PublicShow source

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
Source add_to_heap(+Heap0, +Priority, ?Key, -Heap) is semidet
Adds Key with priority Priority to Heap0, constructing a new heap in Heap.
Source 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.
Source empty_heap(?Heap) is semidet
True if Heap is an empty heap. Complexity: constant.
Source singleton_heap(?Heap, ?Priority, ?Key) is semidet
True if Heap is a heap with the single element Priority-Key.

Complexity: constant.

Source 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.
Source heap_size(+Heap, -Size:int) is det
Determines the number of elements in Heap. Complexity: constant.
Source 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)$.
Source is_heap(+X) is semidet
Returns true if X is a heap. Validates the consistency of the entire heap. Complexity: linear.
Source 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.
Source 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.
Source 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.

Source merge_heaps(+Heap0, +Heap1, -Heap) is det
Merge the two heaps Heap0 and Heap1 in Heap. Complexity: constant.