Heap Sort in Prolog
<![CDATA[
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
% Heap Sort in Prolog
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
% Nicolaie Popescu-Bodorin, 2009
% http://fmi.spiruharet.ro/bodorin/
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
% Prolog, TP 2.0
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
DOMAINS
r = real
lr = r*
heap = h(r,heap,heap) ; nil
tree = t(r,tree,tree) ; nil
PREDICATES
hsort(lr,lr) % (i,o), sort the intup list using Heap-sort algorithm
list2heap(lr,heap) % (i,o), convert the input list in a heap
list2heap(lr,heap,heap) % second variable as accumulator
heap2slist(heap,lr) % read sorted list from input heap
insert_in_heap(r,heap,heap)
remove(r,heap,heap)
remove2(r,heap,heap)
tree2heap(heap,heap)
CLAUSES
/* MAIN predicate: Heap Sort Implementation in Prolog:
USAGE:
hsort([4,1,4,13,2,1,3,2,1], SL)
hsort(L, SL), (i,o), (InputList, SortedList) */
hsort(L, SL):- list2heap(L, Heap), heap2slist(Heap, SL).
% Convert the input list in a heap
% list2heap(L, H), (i,o), (InputList, OutputHeap)
list2heap(List, Heap):-list2heap(List, nil, Heap).
list2heap([H|T], Ri, R):- insert_in_heap(H, Ri, Ria), list2heap(T, Ria, R).
list2heap([], Heap, Heap).
% insert_in_heap(V, H1, H2) , (i,i,o), (InputValue, GivenHeap, ResultingHeap)
insert_in_heap(V, h(Root, Left, Right), h(Root, Right, Left2)):-
V >= Root, !, insert_in_heap(V, Left, Left2).
insert_in_heap(V, h(Root, Left, Right), h(V, Right, Left2)):- insert_in_heap(Root, Left, Left2).
insert_in_heap(V, nil, h(V, nil, nil)).
% heap2slist(Heap, List), (i,o), (InputHeap, ResultingSortedList)
heap2slist(nil, []):-!.
heap2slist(H, [X|T]):- remove(X, H, Hi), heap2slist(Hi, T).
% remove(Root, H1, H2), (i,i,o), The output heap H2 is obtained by removing the root from the input heap H1
remove(Root, h(Root, nil, Right), Right):-!.
remove(Root, h(Root, Left, Right), RezHeap):-
remove2(V, Right, Right2),%write(V),nl,
tree2heap(h(V, Right2, Left), RezHeap).
% (o,i,o)
remove2(Root, h(Root, nil, Right), Right):-!.
remove2(V, h(Root, Left, Right), h(Root, Right2, Left)) :- remove2(V, Right, Right2).
% tree2heap(Tree, Heap) , (i,o), convert the input tree (LeftHeap-Root-RightHeap) into an output heap
tree2heap(
h( Root, h(LeftValue, LeftLeft, LeftRight), h(RightValue, RightLeft, RightRight) ),
h(LeftValue, Left, h(RightValue, RightLeft, RightRight)) ):-
RightValue >= LeftValue, Root >= LeftValue, !, tree2heap(h(Root, LeftLeft, LeftRight), Left).
tree2heap( h(Root, Left, h(RightValue, RightLeft, RightRight)), h(RightValue, Left, Right) ):-
Root >= RightValue, !, tree2heap(h(Root, RightLeft, RightRight), Right).
tree2heap(Heap,Heap).
]]>