19 Heap Operations

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.