Next: lib-is_directives, Previous: lib-gauge, Up: The Prolog Library [Contents][Index]

`library(heaps)`

A heap is a labelled binary tree where the key of each node is less
than or equal to the keys of its sons. The point of a heap is that
we can keep on adding new elements to the heap and we can keep on
taking out the minimum element. If there are `N` elements total, the
total time is `O(N lg N)`. If you know all the elements in advance, you
are better off doing a merge-sort, but this file is for when you
want to do say a best-first search, and have no idea when you start
how many elements there will be, let alone what they are.

A heap is represented as a triple `heap(N,Free,Tree)`

where `N` is the
number of elements in the tree, `Free` is a list of integers which
specifies unused positions in the tree, and `Tree` is a tree made of:

`heap`

terms for empty subtrees and

`heap(`

`Key`,`Datum`,`Lson`,`Rson`)terms for the rest

The nodes of the tree are notionally numbered like this:

1 2 3 4 6 5 7 8 12 10 14 9 13 11 15 .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. ..

The idea is that if the maximum number of elements that have been in
the heap so far is `M`, and the tree currently has `K` elements, the tree
is some subtreee of the tree of this form having exactly `M` elements,
and the `Free` list is a list of `M-K` integers saying which of the
positions in the `M`-element tree are currently unoccupied. This free
list is needed to ensure that the cost of passing `N` elements through
the heap is `O(N lg M)` instead of `O(N lg N)`. For `M` say 100 and `N` say 10^4
this means a factor of two. The cost of the free list is slight.
The storage cost of a heap in a copying Prolog is `2K+3M` words.
Exported predicates:

`add_to_heap(`

`+OldHeap`,`+Key`,`+Datum`,`-NewHeap`)`add_to_heap/4 (heaps)`

inserts the new

`Key-Datum`pair into the heap. 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.`delete_from_heap(`

`+OldHeap`,`+Key`,`-Datum`,`-NewHeap`)`delete_from_heap/4 (heaps)`

deletes a single

`Key-Datum`pair from the`OldHeap`producing a`NewHeap`. This is useful if you want to e.g. change the priority of Datum.`get_from_heap(`

`+OldHeap`,`-Key`,`-Datum`,`-NewHeap`)`get_from_heap/4 (heaps)`

returns the

`Key-Datum`pair in`OldHeap`with the smallest`Key`, and also a`NewHeap`which is the`OldHeap`with that pair deleted.`heap_size(`

`+Heap`,`-Size`)`heap_size/2 (heaps)`

reports the number of elements currently in the heap.

`heap_to_list(`

`+Heap`,`-List`)`heap_to_list/2 (heaps)`

returns the current set of

`Key-Datum`pairs in the`Heap`as a`List`, sorted into ascending order of`Keys`.`list_to_heap(`

`+List`,`-Heap`)`list_to_heap/2 (heaps)`

takes a proper list of

`Key-Datum`pairs (such as`keysort/2`

could be used to sort) and forms them into a heap.`empty_heap(`

`?Heap`)`empty_heap/1 (heaps)`

is true when

`Heap`represents an empty heap. There is only one way it can be true.`is_heap(`

`+Heap`)`is_heap/1 (heaps)`

is true when

`Heap`is a well formed heap. For this to be true, the size must be right and the tree must satisfy the heap condition.`min_of_heap(`

`+Heap`,`-Key`,`-Datum`)`min_of_heap/3 (heaps)`

returns the

`Key-Datum`pair at the top of the heap (which is of course the pair with the smallest`Key`), but does not remove it from the heap. It fails if the heap is empty.`min_of_heap(`

`+Heap`,`-Key1`,`-Datum1`,`-Key2`,`-Datum2`)`min_of_heap/5 (heaps)`

returns the smallest (

`Key1`) and second smallest (`Key2`) pairs in the heap, without deleting them. It fails if the heap does not have at least two elements.`portray_heap(`

`+Heap`)`portray_heap/1 (heaps)`

writes a heap to the current output stream in a pretty format so that you can easily see what it is. Note that a heap written out this way can

*not*be read back in. The point of this predicate is that you can add a clauseportray(X) :- is_heap(X), !, portray_heap(X).

Send feedback on this subject.