[OT] Finding longest documents

Christopher Wright dhasenan at gmail.com
Mon Oct 13 18:15:29 PDT 2008


Klaus Oberhofer wrote:
> Andrei Alexandrescu schrieb:
>>
>> 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
> 
> Some time ago I implemented a binary heap because I needed it to create 
> Huffman codes  (Warning: Maybe the code does not catch up to the current 
> Tango library.).  Parts of the code are inspired by the MINTL library, 
> which contains an implementation, too. See my code at
> 
> http://www.dsource.org/projects/nova/browser/trunk/nova/ds/priorityqueue.d
> 
> MINTL seems to be abandoned, but I found it in the necrophilia repos:
> 
> http://necrophilia.googlecode.com/svn/trunk/tests/shared/mintl/arrayheap.d
> 
> 
> KlausO
> 

There isn't a lot you can do to mess up a heap, but there are some minor 
issues with yours:
1. It only has one direction (which isn't documented).
2. It has a key/value pair as its element type.
3. It's only keyed on ints.

My heap was apparently accepted into Tango last week, with some minor 
fixes and cleanup (and switched into a struct rather than a class; not 
sure I like that). The only issue I see with the fixed version is that 
it uses recursion in a couple places where it could loop instead.

Anyway, the code's here: 
http://dsource.org/projects/tango/browser/trunk/tango/util/container/more/Heap.d?rev=3959



More information about the Digitalmars-d mailing list