Node:Heaps, Next:Lists, Previous:Attributes, Up:Top
A binary heap is a tree with keys and associated values that satisfies
the heap condition: the key of every node is greater than or equal
to the key of its parent, if it has one. The main application of
binary heaps are priority queues. To load the package, enter the
query
| ?- use_module(library(heaps)).
add_to_heap(+OldHeap, +Key, +Datum, ?NewHeap)
Inserts the new Key-Datum pair into the current heap
OldHeap producing the new heap NewHeap. The insertion is
not stable, that is, if you insert several pairs with the same
Key it is not defined which of them will come out first, and it is
possible for any of them to come out first depending on the history of
the heap. Example:
| ?- add_to_heap(t(0,[],t),3,678,N). N = t(1,[],t(3,678,t,t))
get_from_heap(+OldHeap, ?Key, ?Datum, ?NewHeap)
Returns the Key-Datum pair in OldHeap with the
smallest Key, and also a NewHeap, which is the OldHeap
with that pair deleted. Example:
get_from_heap(t(1,[],t(1,543,t,t)),K,D,N). D = 543, K = 1, N = t(0,[1],t)
empty_heap(?Heap)
is true when Heap is the empty heap.
heap_size(+Heap, ?Size)
Size is the number of elements in the heap Heap.
heap_to_list(+Heap, -List)
Returns the current set of Key-Datum pairs in the
Heap as a keysorted List.
is_heap(+Heap)
is true when Heap is a valid heap.
list_to_heap(+List, -Heap)
Takes a list List of Key-Datum pairs and
forms them into a heap Heap. Example:
| ?- list_to_heap([1-34,2-345,5-678],H). H = t(3,[],t(1,34,t(2,345,t,t),t(5,678,t,t)))
min_of_heap(+Heap, ?Key, ?Datum)
Returns the Key-Datum pair at the top of the heap
Heap without removing it. Fails if the heap is empty.
min_of_heap(+Heap, ?Key1, ?Datum1, ?Key2, ?Datum2)
Returns the smallest (Key1-Datum1) and second smallest
(Key2-Datum2) pairs in the Heap, without
deleting them. It fails if the heap does not have at least two
elements.
delete_from_heap(+OldHeap, +Key, ?Datum, ?NewHeap)
deletes a single Key-Datum pair in OldHeap producing NewHeap. This is useful if you want to e.g. change the priority of Datum. Beware: this operation needs to search the whole heap in the worst case.