Invisible <voi### [at] devnull> wrote:
> 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.)

  Your tree data structure can have a reference/handle to the first and
last elements for fast access (which is, in fact, what eg. std::set and
std::map do, in order to be able to get the iterators to the first and
last elements fast). In this case you get fast access to the smallest,
largest and median elements (the root node is obviously the median in
a balanced binary search tree).

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

  A heap is at least much *simpler* to implement (and requires less
ancillary data) than a balanced binary search tree. However, the fact
that you can construct a heap on an array without any ancillary data
whatsoever is still, IMO, by far its biggest advantage as a data structure
in such a case (ie. a priority queue). You lose much of that efficiency
if you allocate all the nodes separately.

> 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).

  I assume that means that Haskell doesn't handle objects (if it even has
such a concept) by value, only by reference (which, in fact, isn't very
surprising to me).

> 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...

  Sometimes low-level efficiency means you have to bypass fancy
abstractions...

-- 
                                                          - Warp

Post a reply to this message