Huffman coding for rosetta code entry #code-review


Hi there,

on my way learning Rust I was digging in some basic algorithm and I found out that the Huffman coding entry in Rosetta code wiki doesn’t include a Rust implementation. So I decided to give it a try:

Since this is my first Rust code with some common sense in it I would like to ask for code review before creating the entry in Rosetta code wiki.

Of course many thanks to all the people that helped me out on #rust-beginners and #rust channels.




This looks pretty good to me. One minor change I would make, just to shorten some code, is to replace this:

let mut p = "";

match i {
    0 => p = "0", // left node
    1 => p = "1", // right node
    _ => (),

with this:

let p = match i {
    0 => "0", // left node
    1 => "1", // right node
    _ => "",

Edit: Also, perhaps instead of a Vec of children, Node::Internal should have left_child and right_child fields.


many thanks @mbrubeck ! that makes totally sense to me.


Why this is not in Rosetta code wiki already? :disappointed:



I like using a fixed size array when left/right child members come up. This enables both static checking that you have exactly 2 children (of course), but it also makes it possible to generalize some algorithms, but iterating over the array, or using k and 1 - k to access the children (where k is either 0 or 1). It lets you exploit symmetries to avoid repetition, simply. (I learned this from @ )


@bluss that was actually the idea since I’m planning to transform this to an n-ary algorithm. But maybe for the sake of simplicity we can just use left_child and right_child. Still not sure though.


I would second bluss’s idea of using a fixed size array. My only other concern would be the:

let elements = Vec::from(elements);
let mut priority_queue = BinaryHeap::new();


In the create_tree function. I think the elements are being cloned here, and I don’t think that is needed.


Take also a look at the D entry (that beside being short is also quite efficient, it takes a rather short time to build a tree of a million different symbols).


This will move the elements, not copy (speaking rust level semantics). The into_iter for vec ensures this.