[OT] Finding longest documents

[Christopher Wright]

Benji Smith wrote:
> 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
> 

Neither Tango nor Phobos contains a heap implementation. I've submitted 
one to Tango, but I don't think anyone's done anything about it.

My implementation's rather smaller, but that may be due to the number of 
comments yours has. The comment lines and code lines are approaching 
parity in yours. I believe that mine also releases memory if you add a 
lot to it and subsequently remove a lot from it.