std.algorithm.BinaryHeap

[bearophile]

I have tried to use BinaryHeap of Phobos2. As a warming up exercise I am translating this little Python program to D2 using Phobos2 only, a very basic Huffman encoder:

from heapq import heappush, heappop, heapify
from collections import defaultdict

def encode(freqs):
    """Huffman encode the given dict mapping symbols to weights"""
    heap = [[float(wt), [sym, '']] for sym,wt in freqs.iteritems()]
    heapify(heap)
    while len(heap) > 1:
        lo = heappop(heap)
        hi = heappop(heap)
        for i in lo[1:]:
            i[1] = '0' + i[1]
        for i in hi[1:]:
            i[1] = '1' + i[1]
        lohi = [lo[0] + hi[0]] + lo[1:] + hi[1:]
        heappush(heap, lohi)
    return sorted(heappop(heap)[1:], key=lambda x: (len(x[-1]), x))

astring = "this is an example for huffman encoding"
freqs = defaultdict(int)
for c in astring:
    freqs[c] += 1
huff = encode(freqs)
print "SYMBOL\tWEIGHT\tHUFFMAN CODE"
for h in huff:
    print "'%s'\t%s\t%s" % (h[0], freqs[h[0]], h[1])

That outputs is:
SYMBOL	WEIGHT	HUFFMAN CODE
' '	6	101
'n'	4	010
'a'	3	1001
'e'	3	1100
'f'	3	1101
'h'	2	0001
'i'	3	1110
'm'	2	0010
'o'	2	0011
's'	2	0111
'g'	1	00000
'l'	1	00001
'p'	1	01100
'r'	1	01101
't'	1	10000
'u'	1	10001
'x'	1	11110
'c'	1	111110
'd'	1	111111

(Note that the python heap isn't object oriented, I'd like to write it in C for Python2.6, in the meantime if you need OOP you can use http://code.activestate.com/recipes/502295/ ).

Regarding BinaryHeap of Phobos2:

This may be a dumb question: How do you push/add an item to such heap (to translate the heappush)? I have found no info in the docs.

I suggest to add one or two examples of the acquire(Range r) method, because I don't understand its purpose.

I suggest to add to the std.algorithm module something like:

BinaryHeap!(Range) binaryHeap(Range)(Range arr) {
    return BinaryHeap!(Range)(arr);
}

Otherwise most of the times you have to use:
auto heap = BinaryHeap!(typeof(arr))(arr);

(In the following few months I'll probably post many more notes about Phobos2).

Bye,
bearophile