>>>> Then the old heap is in oldheap and the new heap is in newheap.
>>>
>>>     Is this supposed to be efficient?
>
>> Modifying log N nodes of the old heap to construct the new one? I'd say
>> it's reasonably efficient, yes.
>
>    Not modifying. *Copying*. There's a huge difference.

Not really. We're talking about 4 machine words. Modifying one of those 
words would be faster than copying all 4 of them, but I doubt that the 
speed difference is astronomical. I'm sure C++ passes bigger structs 
than that by value all the time...

> (All in-place data
> containers and algorithms *modify* the elements, that's not the problem.
> The problem I see there with Haskell is that it *copies* the elements.)
>
>    (Also: Imagine that the elements of the heap had some mutable data
> container in them. Of course that's not purely functional anymore, but
> AFAIK that's *possible* in Haskell. How can you avoid having to copy the
> entire tree when you insert or remove a node? It's not like the new heap
> and the old heap could share some of the nodes, because if you modify the
> mutable container of one of those nodes, the other heap is going to see
> the modification.)

I'm not really following what you're trying to say here.

If you're saying "immutable structures are inefficient", I'd have to say 
that I'll take the vast increase in reliability, maintainability, 
flexibility and so forth over a few percent performance hit.

If you're saying "if you put mutable data into an immutable container, 
things can go wrong", I'd say don't do that. Unless you really clearly 
understand the implications and there's some advantage to doing it this way.

I would like to point out that the whole /benefit/ of a min-heap is that 
it provides O(1) access to the minimum element. Well, that's only 
possible because of the heap invariant - i.e., because data is stored in 
semi-sorted order. If you can mutate the elements, you can trivially 
break that invariant.

If you implemented this in Java or Pascal, you'd write a note in the 
documentation saying "please don't mutate the elements in a way that 
changes their relative ordering". In Haskell, you can make it so people 
/can't/ change the relative ordering.

Post a reply to this message