10.10 Heap Operations—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 clause

              portray(X) :- is_heap(X), !, portray_heap(X).