`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 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.