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.