% File : HEAPS.PL % Author : R.A.O'Keefe % Updated: 29 November 1983 % Purpose: Implement heaps in Prolog. /* 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. */ % add_to_heap(+OldHeap, +Key, +Datum, -NewHeap) % 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. If you need a stable heap, 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 empty, the tree will % be grown, otherwise one of the empty slots will be re-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.) add_to_heap(t(M,,OldTree), Key, Datum, t(N,,NewTree)) :- !, N is M+1, add_to_heap(N, Key, Datum, OldTree, NewTree). add_to_heap(t(M,[H|T],OldTree), Key, Datum, t(N,T,NewTree)) :- N is M+1, add_to_heap(H, Key, Datum, OldTree, NewTree). add_to_heap(1, Key, Datum, _, t(Key,Datum,t,t)) :- !. add_to_heap(N, Key, Datum, t(K1,D1,L1,R1), t(K2,D2,L2,R2)) :- E is N mod 2, M is N div 2, sort2(Key, Datum, K1, D1, K2, D2, K3, D3), add_to_heap(E, M, K3, D3, L1, R1, L2, R2). add_to_heap(0, N, Key, Datum, L1, R, L2, R) :- !, add_to_heap(N, Key, Datum, L1, L2). add_to_heap(1, N, Key, Datum, L, R1, L, R2) :- !, add_to_heap(N, Key, Datum, R1, R2). sort2(Key1, Datum1, Key2, Datum2, Key1, Datum1, Key2, Datum2) :- Key1 @< Key2, !. sort2(Key1, Datum1, Key2, Datum2, Key2, Datum2, Key1, Datum1). % get_from_heap(+OldHeap, ?Key, ?Datum, -NewHeap) % returns the Key-Datum pair in OldHeap with the smallest Key, and % also a New Heap which is the Old Heap with that pair deleted. % The easy part is picking off the smallest element. The hard part % is repairing the heap structure. repair_heap/4 takes a pair of % heaps and returns a new heap built from their elements, and the % position number of the gap in the new tree. Note that repair_heap % is *not* tail-recursive. get_from_heap(t(N,Free,t(Key,Datum,L,R)), Key, Datum, t(M,[Hole|Free],Tree)) :- M is N-1, repair_heap(L, R, Tree, Hole). repair_heap(t(K1,D1,L1,R1), t(K2,D2,L2,R2), t(K2,D2,t(K1,D1,L1,R1),R3), N) :- K2 @< K1, !, repair_heap(L2, R2, R3, M), N is 2*M+1. repair_heap(t(K1,D1,L1,R1), t(K2,D2,L2,R2), t(K1,D1,L3,t(K2,D2,L2,R2)), N) :- !, repair_heap(L1, R1, L3, M), N is 2*M. repair_heap(t(K1,D1,L1,R1), t, t(K1,D1,L3,t), N) :- !, repair_heap(L1, R1, L3, M), N is 2*M. repair_heap(t, t(K2,D2,L2,R2), t(K2,D2,t,R3), N) :- !, repair_heap(L2, R2, R3, M), N is 2*M+1. repair_heap(t, t, t, 1) :- !. % heap_size(+Heap, ?Size) % reports the number of elements currently in the heap. heap_size(t(Size,_,_), Size). % heap_to_list(+Heap, -List) % returns the current set of Key-Datum pairs in the Heap as a % List, 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 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, where we can exploit the fact that the tops % of the subtrees are smaller than their descendants. heap_to_list(t(_,_,Tree), List) :- heap_tree_to_list(Tree, List). heap_tree_to_list(t, ) :- !. heap_tree_to_list(t(Key,Datum,Lson,Rson), [Key-Datum|Merged]) :- heap_tree_to_list(Lson, Llist), heap_tree_to_list(Rson, Rlist), heap_tree_to_list(Llist, Rlist, Merged). heap_tree_to_list([H1|T1], [H2|T2], [H2|T3]) :- H2 @< H1, !, heap_tree_to_list([H1|T1], T2, T3). heap_tree_to_list([H1|T1], T2, [H1|T3]) :- !, heap_tree_to_list(T1, T2, T3). heap_tree_to_list(, T, T) :- !. heap_tree_to_list(T, , T). % 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, but % this algorithm makes it obvious that the result is a heap, and % could be adapted for use when the ordering predicate is not @< % and hence keysort is inapplicable. list_to_heap(List, Heap) :- list_to_heap(List, 0, t, Heap). list_to_heap(, N, Tree, t(N,,Tree)) :- !. list_to_heap([Key-Datum|Rest], M, OldTree, Heap) :- N is M+1, add_to_heap(N, Key, Datum, OldTree, MidTree), list_to_heap(Rest, N, MidTree, Heap). % min_of_heap(+Heap, ?Key, ?Datum) % 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) % 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. min_of_heap(t(_,_,t(Key,Datum,_,_)), Key, Datum). min_of_heap(t(_,_,t(Key1,Datum1,Lson,Rson)), Key1, Datum1, Key2, Datum2) :- min_of_heap(Lson, Rson, Key2, Datum2). min_of_heap(t(Ka,Da,_,_), t(Kb,Db,_,_), Kb, Db) :- Kb @< Ka, !. min_of_heap(t(Ka,Da,_,_), _, Ka, Da). min_of_heap(t, t(Kb,Db,_,_), Kb, Db).