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(NlgN). 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.

The following heap manipulation routines are available once included with the use_module(library(heaps)) command.

  • add_to_heap//44

  • empty_heap//11

  • get_from_heap//44

  • heap_size//22

  • heap_to_list//22

  • list_to_heap//22

  • min_of_heap//33

  • min_of_heap//55

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(NlgN). 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 t(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 t terms for empty subtrees and t(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 K-M 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(NlgM) instead of O(NlgN). 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 (which Dec-10 Prolog is not) is 2K+3M words.

Functions:

1. *** prolog::add_to_heap(OldHeap, Key, Datum, NewHeap) %% inserts the new Key-Datum pair into the heap. The insertion is% not stable*:

1. that if you insert several pairs with the same Key it is not defined which of them will come out and it is possible for any of them to come out first depending on the history of the heap If you need a stable you could add a counter to the heap and include the counter at the time of insertion in the key If the free list is the tree will be otherwise one of the empty slots will be re prolog::used(I% use imperative programming language, but the heap code is as % pure as the trees code, you can create any number of variants% starting from the same heap, and they will share what common% structure they can without interfering with each other.) class add_to_heap_4:

1. pred prolog::get_from_heap(+Heap,- key,- Datum,- Heap) %% returns the Key-Datum pair in OldHeap with the smallest Key:

1. prolog::get_from_heap_4::get_from_heap/4(int ARG1, int ARG2, int ARG3, int ARG4)():

1. *** prolog::heap_to_list(+Heap, - List) %% returns the current set of Key-Datum pairs in the Heap as a% List*:

1. sorted into ascending order of Keys This is included simply because I think every data structure foo ought to have a foo_to_list and list_to_foo prolog::relation(where, of course, it% makes sense!) so that conversion between arbitrary data% structures is as easy as possible. This predicate is basically% just a merge sort:

1. prolog::heap_to_list_2::heap_to_list/2(int ARG1, int ARG2)():

1. *** prolog::list_to_heap(+List, - Heap) %% takes a list of Key-Datum pairs(such as keysort could be used to% sort) and forms them into a heap. We could do that a wee bit% faster by keysorting the list and building the tree directly*:

Var:

1. that prolog::is:

1. that if you insert several pairs with the same Key it is not defined which of them will come out prolog::first:

1. but this algorithm makes it obvious that the result is a prolog::heap:

1. Product If Set1 and Set2 are ordered Product will be an ordered set of x1 x2 pairs Note that we cannot solve for Set1 and because there are infinitely many solutions when Product is prolog::empty:

1. that if you insert several pairs with the same Key it is not defined which of them will come out and it is possible for any of them to come out first depending on the history of the heap If you need a stable you could add a counter to the heap and include the counter at the time of insertion in the key If the free list is the tree will be prolog::grown: