% P63 (**) Construct a complete binary tree
%
% A complete binary tree with height H is defined as follows:
% The levels 1,2,3,...,H-1 contain the maximum number of nodes
% (i.e 2**(i-1) at the level i, note that we start counting the
% levels from 1 at the root). In level H, which may contain less
% than the maximum number possible of nodes, all the nodes are
% "left-adjusted". This means that in a levelorder tree traversal
% all internal nodes come first, the leaves come second, and
% empty successors (the nils which are not really nodes!)
% come last. Complete binary trees are used for heaps.
:- ensure_loaded(p57).
% complete_binary_tree(N,T) :- T is a complete binary tree with
% N nodes. (+,?)
complete_binary_tree(N,T) :- complete_binary_tree(N,T,1).
complete_binary_tree(N,nil,A) :- A > N, !.
complete_binary_tree(N,t(_,L,R),A) :- A =< N,
AL is 2 * A, AR is AL + 1,
complete_binary_tree(N,L,AL),
complete_binary_tree(N,R,AR).
% ----------------------------------------------------------------------
% This was the solution of the exercise. What follows is an application
% of this result.
% We define a heap as a term heap(N,T) where N is the number of elements
% and T a complete binary tree (in the sense used above).
% The conservative usage of a heap is first to declare it with a predicate
% declare_heap/2 and then use it with a predicate element_at/3.
% declare_heap(H,N) :-
% declare H to be a heap with a fixed number N of elements
declare_heap(heap(N,T),N) :- complete_binary_tree(N,T).
% element_at(H,K,X) :- X is the element at address K in the heap H.
% The first element has address 1.
% (+,+,?)
element_at(heap(_,T),K,X) :-
binary_path(K,[],BP), element_at_path(T,BP,X).
binary_path(1,Bs,Bs) :- !.
binary_path(K,Acc,Bs) :- K > 1,
B is K /\ 1, K1 is K >> 1, binary_path(K1,[B|Acc],Bs).
element_at_path(t(X,_,_),[],X) :- !.
element_at_path(t(_,L,_),[0|Bs],X) :- !, element_at_path(L,Bs,X).
element_at_path(t(_,_,R),[1|Bs],X) :- element_at_path(R,Bs,X).
% We can transform lists into heaps and vice versa with the following
% useful predicate:
% list_heap(L,H) :- transform a list into a (limited) heap and vice versa.
list_heap(L,H) :- is_list(L), list_to_heap(L,H).
list_heap(L,heap(N,T)) :- integer(N), fill_list(heap(N,T),N,1,L).
list_to_heap(L,H) :-
length(L,N), declare_heap(H,N), fill_heap(H,L,1).
fill_heap(_,[],_).
fill_heap(H,[X|Xs],K) :- element_at(H,K,X), K1 is K+1, fill_heap(H,Xs,K1).
fill_list(_,N,K,[]) :- K > N.
fill_list(H,N,K,[X|Xs]) :- K =< N,
element_at(H,K,X), K1 is K+1, fill_list(H,N,K1,Xs).
% However, a more aggressive usage is *not* to define the heap in the
% beginning, but to use it as a partially instantiated data structure.
% Used in this way, the number of elements in the heap is unlimited.
% This is Power-Prolog!
% Try the following and find out exactly what happens.
% ?- element_at(H,5,alfa), element_at(H,2,beta), element(H,5,A).
% -------------------------------------------------------------------------
% Test section. Suppose you have N elements in a list which must be looked
% up M times in a random order.
test1(N,M) :-
length(List,N), lookup_list(List,N,M).
lookup_list(_,_,0) :- !.
lookup_list(List,N,M) :-
K is random(N)+1, % determine a random address
nth1(K,List,_), % look up and throw away
M1 is M-1,
lookup_list(List,N,M1).
% ?- time(test1(100,100000)).
% 1,384,597 inferences in 3.98 seconds (347889 Lips)
% ?- time(test1(500,100000)).
% 4,721,902 inferences in 13.82 seconds (341672 Lips)
% ?- time(test1(10000,100000)).
% 84,016,719 inferences in 277.51 seconds (302752 Lips)
test2(N,M) :-
declare_heap(Heap,N),
lookup_heap(Heap,N,M).
lookup_heap(_,_,0) :- !.
lookup_heap(Heap,N,M) :-
K is random(N)+1, % determine a random address
element_at(Heap,K,_), % look up and throw away
M1 is M-1,
lookup_heap(Heap,N,M1).
% ?- time(test2(100,100000)).
% 3,002,061 inferences in 7.81 seconds (384387 Lips)
% ?- time(test2(500,100000)).
% 4,097,961 inferences in 10.75 seconds (381206 Lips)
% ?- time(test2(10000,100000)).
% 6,366,206 inferences in 19.16 seconds (332265 Lips)
% Conclusion: In this scenario, for lists longer than 500 elements
% it is more efficient to use a heap.