Created
July 26, 2010 11:51
-
-
Save seancribbs/490447 to your computer and use it in GitHub Desktop.
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
%% Based on Okasaki 6.2.2 | |
-module(binomial_heap). | |
-export([insert/2, insert/3, merge/2, delete/1, to_list/1, take/2,esize/1]). | |
-record(node,{rank,key,value,children=[]}). | |
% Inserts a new pair into the heap (or creates a new heap) | |
insert(Key,Value) -> | |
insert(Key,Value,[]). | |
insert(Key,Value,Forest) -> | |
insTree(#node{rank=0,key=Key,value=Value},Forest). | |
% Merges two heaps | |
merge(TS1,[]) when is_list(TS1) -> TS1; | |
merge([],TS2) when is_list(TS2) -> TS2; | |
merge([#node{rank=R1}=T1|TS1]=F1,[#node{rank=R2}=T2|TS2]=F2) -> | |
if | |
R1 < R2 -> | |
[T1 | merge(TS1,F2)]; | |
R2 < R1 -> | |
[T2 | merge(F1, TS2)]; | |
true -> | |
insTree(link(T1,T2),merge(TS1,TS2)) | |
end. | |
% Deletes the top entry from the heap and returns it | |
delete(TS) -> | |
{#node{key=Key,value=Value,children=TS1},TS2} = getMin(TS), | |
{{Key,Value},merge(lists:reverse(TS1),TS2)}. | |
% Turns the heap into list in heap order | |
to_list([]) -> []; | |
to_list(List) when is_list(List) -> | |
to_list([],List). | |
to_list(Acc, []) -> | |
lists:reverse(Acc); | |
to_list(Acc,Forest) -> | |
{Next, Trees} = delete(Forest), | |
to_list([Next|Acc], Trees). | |
% Take N elements from the top of the heap | |
take(N,Trees) when is_integer(N), is_list(Trees) -> | |
take(N,Trees,[]). | |
take(0,_Trees,Acc) -> | |
lists:reverse(Acc); | |
take(_N,[],Acc)-> | |
lists:reverse(Acc); | |
take(N,Trees,Acc) -> | |
{Top,T2} = delete(Trees), | |
take(N-1,T2,[Top|Acc]). | |
% Get an estimate of the size based on the binomial property | |
esize(Forest) -> | |
erlang:trunc(lists:sum([math:pow(2,R) || #node{rank=R} <- Forest])). | |
%% Private API | |
link(#node{rank=R,key=X1,children=C1}=T1,#node{key=X2,children=C2}=T2) -> | |
case X1 < X2 of | |
true -> | |
T1#node{rank=R+1,children=[T2|C1]}; | |
_ -> | |
T2#node{rank=R+1,children=[T1|C2]} | |
end. | |
insTree(Tree, []) -> | |
[Tree]; | |
insTree(#node{rank=R1}=T1, [#node{rank=R2}=T2|Rest] = TS) -> | |
case R1 < R2 of | |
true -> | |
[T1|TS]; | |
_ -> | |
insTree(link(T1,T2),Rest) | |
end. | |
getMin([T]) -> | |
{T,[]}; | |
getMin([#node{key=K} = T|TS]) -> | |
{#node{key=K1} = T1,TS1} = getMin(TS), | |
case K < K1 of | |
true -> {T,TS}; | |
_ -> {T1,[T|TS1]} | |
end. |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment