[OT] Finding longest documents

[Benji Smith]

Andrei Alexandrescu wrote:
> One nice touch is that you don't even bother to sort the heap; you only 
> remove from it. I wonder if this will be overall sensibly faster than 
> just heapsorting the heap. Thoughts?

I should have mentioned...

The heap doesn't need to be sorted. Anytime you remove an element from 
the heap, it's guaranteed to have the highest value. That's the nice 
thing about the heap. Multiple consecutive removals of the topmost item 
is functionally identical to sorting it in descending order.

Of course, every time you remove the topmost item, it has a cost of log 
n, where n is the number of remaining items in the heap. But sorting the 
whole heap would cost n log n anyhow, so the iterative removal process 
is actually slightly less expensive (since n decreases with every 
iteration).

I actually don't have the code implemented in D, but I've attached my 
Java implementation, so you can get an idea of how it works.

--benji
-------------- next part --------------
An embedded and charset-unspecified text was scrubbed...
Name: BinaryHeap.java
URL: <http://lists.puremagic.com/pipermail/digitalmars-d/attachments/20081012/23c2dec6/attachment.ksh>