[OT] Finding longest documents

[Andrei Alexandrescu]

Christopher Wright wrote:
> 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.

There are heap primitives in std.algorithm, just not published yet. 
Anyhow, in case you or anyone would be interested in putting your ideas 
in Phobos, I encourage you to share some code with me so I can look over it.

Andrei