-
Notifications
You must be signed in to change notification settings - Fork 5
/
chp3.erl
79 lines (65 loc) · 2.22 KB
/
chp3.erl
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
-module(chp3).
-compile(export_all).
%% exercise 3.1, pg 18
%% prove the right spine of a leftist heap of size n has at most [log(n+1)] elements
%% Heap: {Rank, N, Lheap, Rheap}
merge(H, {}) -> H;
merge({}, H) -> H;
merge({_RankA, X, La, Ra}, {_RankB, Y, _Lb, _Rb}=Hb) when X =< Y ->
makeT(X, La, merge(Ra, Hb));
merge(Ha, {_RankB, Y, Lb, Rb}) ->
makeT(Y, Lb, merge(Ha, Rb)).
%% rank
rank({}) -> 0;
rank({Rank, _X, _Lheap, _Rheap}) -> Rank.
%% calculates the rank of a Heap node and swaps children if necessary
makeT(X, Lheap, Rheap) ->
Lrank = rank(Lheap),
Rrank = rank(Rheap),
if Lrank >= Rrank ->
{Rrank + 1, X, Lheap, Rheap};
true -> { Lrank + 1, X, Rheap, Lheap }
end.
%% insert creates a singleton heap and merges it with the main heap
insert(X, H) -> merge({0, X, {}, {}}, H).
findMin({_Rank, X, _Lheap, _Rheap}) -> X;
findMin(_) -> throw("Error: Bad Heap passed").
deleteMin({_Rank, _X, Lheap, Rheap}) ->
merge(Lheap, Rheap);
deleteMin(_) -> throw("Error: Bad Heap passed").
%% exercise 3.2, pg 19
%% define insert directly without calling merge
calc_rank({}) -> 0;
calc_rank({_Rank, _X, _Left, Right}) ->
calc_rank(Right, 1).
calc_rank({}, Rank) -> Rank - 1;
calc_rank({_Rank, _X, _Left, {}}, R) -> R;
calc_rank({_Rank, _X, _Left, Right}, R) ->
calc_rank(Right, R).
insert2(X, {}) -> {0, X, {}, {}};
insert2(X, {_Rank, Y, _Lheap, _Rheap}=H) when X =< Y ->
{1, X, H, {}};
insert2(X, {Rank, Y, Lheap, Rheap}) ->
NewRheap = insert2(X, Rheap),
NewRank = calc_rank(NewRheap),
LeftRank = calc_rank(Lheap),
if
LeftRank >= NewRank ->
{NewRank + 1, Y, Lheap, NewRheap};
true ->
{Rank + 1, Y, NewRheap, Lheap}
end.
%% exercise 3.3, pg. 19
%% fromList produces a leftist heap from an unordered list of elements
%% merge heaps in log n passes instead of 1 foldl/r pass
fromList(L) ->
Heaps = lists:map(fun(X) -> insert(X, {}) end, L),
build(Heaps, []).
build([], [Heap]) -> Heap;
build([Heap], []) -> Heap;
build([], [Heap1, Heap2 | Heaps]) ->
build( [merge(Heap1, Heap2) | Heaps], []);
build([H], [Heap | Heaps]) ->
build([merge(H, Heap) | Heaps], []);
build([H1, H2 | T], Heap) ->
build(T, [merge(H1, H2) | Heap]).