|
![](/i/fill.gif) |
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
|
![](/i/fill.gif) |