On 12/10/2010 04:48 PM, Warp wrote:

>    What are the advantages of a heap compared to a balanced binary search
> tree in Haskell?

I hadn't really thought about it.

However, now that I'm thinking about it, the thing that occurs to me is 
that finding the minimum or maximum element of a binary search tree 
presumably requires O(log N) operations, while for a min-heap you can 
find the minimum in O(1) operations. (Similarly, you can find the 
maximum of a max-heap in O(1) time.)

So if you're doing something like implementing a priority queue or 
similar, a heap looks like being a better choice than a BST.

On the other hand, I'm not intimately familiar with the various kinds of 
BSTs and their detailed properties...

>    The reason heaps are sometimes used in imperative languages is because
> a heap can be constructed inside an array without requiring any ancillary
> data whatsoever.
>
>    However, Haskell doesn't use (mutable) arrays, so you have to do it
> as a regular tree, with each node allocated separately and containing
> references and whatever ancillary data.

You could do it as a mutable array (but nobody will). More to the point, 
the easiest way to do it is a mutable array of pointers, which still has 
the overhead (although I guess you avoid needing the child pointers). If 
you want (say) a heap of integers represented as just an array of 
unboxed integers, you're going to have to do a fair bit of leg-work in 
Haskell. Sadly...

Post a reply to this message