Some pseudo code or resources will be appreciated.I was thinking if implementing it in form of a BST stored in an array. However,not all operations can be performed easily using this approach. I am open to using STL's for this purpose as well.My main purpose is to implement it in the simplest manner possible.

  • There's a complete example in C++ at github.com/ikalnitsky/yaahc which uses it's own custom tree using the FGK algorithm. Are you looking for something different than that? Or do you just want to write your own from scratch?
    – Danack
    Commented May 5, 2013 at 22:32
  • @Danack:I want to write my own code from scratch using a very simple and probably a very inefficient implementation
    – king_kong
    Commented May 6, 2013 at 4:53

1 Answer 1


My understanding of adaptive Huffman coding is that its implementation requires a weighted tree, and then weights are being operated on, so a standard binary tree, or binary search tree, or a heap, cannot be used 'as is'. In fact, a BST doesn't seem very appropriate, whereas a heap might be a good start, given that (in Vitter's algorithm at least) nodes must be listed in order of decreasing weight, which is reminiscent of a max heap structure... Also, that one set of slides describing implementation details might be useful.

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.