"ocaml_beginners"::[] min-heap algorithm

On Sun, 26 Nov 2006, drehman27 wrote:

> Hi,
>
> Is there a good min-heap implementation available?
>
>; Thanks.

I'm not sure if there is one around already written, but this isn't hard
to write. A good implementation of this is a function leftist queue. The
core operation is the "join", which joins two queues to make one big
queue. Each queue is a tree- trees are either empty (and contain no
elements) or are comprised of a root element and two subtrees. The join
of two empty trees is the empty tree. The join of an empty tree with a
non-empty tree is just the non-empty tree. To join two non-empty trees,
you compare the root elements of the two trees, and the higher priority
element becomes the root element of the combined tree. This leaves you
with three subtrees (the shorter of the two original trees and the two
subtrees from the taller of the two original trees). The tallest of the
three subtrees becomes the left subtree of the combined tree, the right
subtree is then the join of the two shorter trees.

It's easy to see that the join operation is O(log N), once you observe
that although the tree is unbalanced, join always wants to go down the
"shorter branch"- and thus the more unbalanced it is, oddly enough, the
better the algorithm performs. A perfectly balanced tree is, in fact, the
worst case performance case.

The highest priority object in the queue is always the root element of the
tree. To remove the highest priority object, you replace the tree with
the join of the two subtrees. To add an element, you place it in a tree
of 1 element and then join it with the main tree.

This is actually less complicated in Ocaml than it is in English:

module MinHeap(Ord: Map.OrderedType) = struct

type t =
| Empty
| Tree of int * t * Ord.t * t
;;

let height = function
| Empty -> 0 (* empty trees have a height of 0 *)
| Tree(h, _, _, _) -> h
;;

let make l e r =
let h = max (height l) (height r) in
Tree(h, l, e, r)
;;

let rec join l r =
match l, r with
| Empty, Empty -> Empty
| Empty, Tree(_) -> r
| Tree(_), Empty -> l
| Tree(_, l1, e1, r1), Tree(_, l2, e2, r2) ->
if (Ord.compare e1 e2) <= 0 then
(* promote l *)
join3 e1 l1 r1 r
else
(* promote r *)
join3 e2 l l2 r2
and join3 e a b c =
if (height a) >= (height b) then
if (height a) >= (height c) then
(* a is the tallest child *)
make a e (join b c)
else
(* c is the tallest child *)
make c e (join a b)
else
if (height b) >= (height c) then
(* b is the tallest child *)
make b e (join a c)
else
(* c is the tallest child *)
make c e (join a b)
;;

let empty = Empty;;

let add queue elem = join queue (make Empty elem Empty);;

let head = function
| Empty -> invalid_arg "head"
| Tree(_, _, e, _) -> e
;;

let remhead = function
| Empty -> invalid_arg "remhead"
| Tree(_, l, _, r) -> join l r
;;

end;;

Brian

Messages in this topic (2) Reply (via web post) | Start a new topic

.

Thank you Brian and Remi.
I will be constructing min-heaps with an average size of 700 float
numbers. The operations I will be doing most are inserting an element
and removing the min. I wonder if binomial heaps or fibonacci heaps
should be considered in this case.

--- In ocaml_beginners%40yahoogroups.com">ocaml_beginnersyahoogroups.com, Brian Hurt <bhurt...> wrote:
&gt;
>
>
> On Sun, 26 Nov 2006, drehman27 wrote:
&gt;
> > Hi,
> >
> > Is there a good min-heap implementation available?
> >
> > Thanks.
&gt;
> I'm not sure if there is one around already written, but this isn't
hard
> to write. A good implementation of this is a function leftist
queue. The
> core operation is the "join", which joins two queues to make one big
> queue. Each queue is a tree- trees are either empty (and contain no
> elements) or are comprised of a root element and two subtrees. The
join
> of two empty trees is the empty tree. The join of an empty tree with a
> non-empty tree is just the non-empty tree. To join two non-empty
trees,
> you compare the root elements of the two trees, and the higher priority
> element becomes the root element of the combined tree. This leaves you
> with three subtrees (the shorter of the two original trees and the two
> subtrees from the taller of the two original trees). The tallest of
the
> three subtrees becomes the left subtree of the combined tree, the right
> subtree is then the join of the two shorter trees.
&gt;
> It's easy to see that the join operation is O(log N), once you observe
> that although the tree is unbalanced, join always wants to go down the
> "shorter branch&quot;- and thus the more unbalanced it is, oddly enough, the
> better the algorithm performs. A perfectly balanced tree is, in
fact, the
> worst case performance case.
>;
> The highest priority object in the queue is always the root element
of the
> tree. To remove the highest priority object, you replace the tree with
> the join of the two subtrees. To add an element, you place it in a
tree
> of 1 element and then join it with the main tree.
>;
> This is actually less complicated in Ocaml than it is in English:
>
> module MinHeap(Ord: Map.OrderedType) = struct
&gt;
> type t =
> | Empty
>; | Tree of int * t * Ord.t * t
> ;;
>
> let height = function
> | Empty -> 0 (* empty trees have a height of 0 *)
> | Tree(h, _, _, _) -> h
> ;;
>
> let make l e r =
> let h = max (height l) (height r) in
> Tree(h, l, e, r)
> ;;
>
> let rec join l r =
> match l, r with
> | Empty, Empty -> Empty
>; | Empty, Tree(_) -> r
> | Tree(_), Empty -> l
> | Tree(_, l1, e1, r1), Tree(_, l2, e2, r2) ->
>; if (Ord.compare e1 e2) <= 0 then
> (* promote l *)
> join3 e1 l1 r1 r
> else
&gt; (* promote r *)
> join3 e2 l l2 r2
> and join3 e a b c =
> if (height a) >= (height b) then
> if (height a) >= (height c) then
> (* a is the tallest child *)
> make a e (join b c)
> else
&gt; (* c is the tallest child *)
> make c e (join a b)
> else
>; if (height b) >= (height c) then
> (* b is the tallest child *)
> make b e (join a c)
> else
&gt; (* c is the tallest child *)
> make c e (join a b)
> ;;
>
> let empty = Empty;;
&gt;
> let add queue elem = join queue (make Empty elem Empty);;
>
> let head = function
> | Empty -> invalid_arg "head"
>; | Tree(_, _, e, _) -> e
> ;;
>
> let remhead = function
> | Empty -> invalid_arg "remhead"
> | Tree(_, l, _, r) -> join l r
> ;;
>
> end;;
>;
> Brian
>;

Messages in this topic (4) Reply (via web post) | Start a new topic

.

I am having some trouble trying Brian's module in my code:
module MinHeap(Ord: Map.OrderedType) = struct

This is a functor that takes a structure that adheres to the
Map.OrderedType signature and returns a structure.

Could you please give me an example of how to use it in a hypothetical
module M that I want to define?

thanks.

Messages in this topic (9) Reply (via web post) | Start a new topic

.