Invisible <voi### [at] devnull> wrote:
> For those who do not grok Haskell, let me summarise thus:

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

  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 (in other words, the array contains the elements and
nothing else; the order of the elements can be heapified in-place, without
any ancillary data or extra memory), which makes it extremely efficient
(both memorywise, rather obviously, and also speedwise).

  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.

-- 
                                                          - Warp

Post a reply to this message