Huffman Coding

Huffman coding constructs a binary prefix-free code minimizing weighted codeword length for given symbol frequencies. No codeword is a prefix of another, so concatenated codewords can be decoded unambiguously by walking a binary tree. The two-smallest merge rule is the optimal merge pattern with an explicit tree and bit labels. This program prints deterministic codes and their weighted cost.

Prerequisites: Optimal Merge Pattern; binary trees; min-heaps; strings.

Build the idea

1. Represent a prefix-free tree

   Each symbol is a leaf; internal nodes have left and right children. Label left edges 0 and right edges 1. A root-to-leaf bit path is a codeword, and a leaf cannot be an ancestor of another leaf, establishing prefix-freeness. Positive frequencies are required for supplied distinct symbols; missing symbols have no codeword. The one-symbol convention here uses code 0 rather than an empty word.

2. Build by frequency merges

   Push one node per symbol into a min-heap keyed by frequency and creation index. Remove the smallest two, make them children of a new node with summed frequency, and insert the parent. Repeat to one root. Integer creation indices make equal-frequency ties deterministic without suggesting the optimum code is unique.

   $$\mathrm{encodedBits}=\Sigma \mathrm{frequency}\left[s\right]·\mathrm{codeLength}\left[s\right]$$

3. Correctness proof: deepest siblings

   Any optimal full binary prefix tree can place the two least-frequent symbols at a deepest sibling pair without increasing weighted path length: swapping a smaller weight deeper has nonpositive cost change. Contracting these siblings yields a symbol whose frequency is their sum, with the original objective equal to the contracted objective plus that sum. An optimal smaller tree is therefore necessary, and induction justifies every Huffman merge. The one-symbol nonempty-code convention is handled separately.

4. Trace and produce codes

   Frequencies a:5,b:7,c:10,d:15 merge 5+7=12, then 10+12=22, then 15+22=37. With smaller heap entries placed left, d gets 0, c gets 10, a gets 110 and b gets 111. Weighted cost is 5·3+7·3+10·2+15·1=71. An explicit iterative stack walks the built tree, so the program outputs actual codewords, not merely a merge-cost number.

   Symbol	Frequency	Code	Weighted bits
   a	5	110	15
   b	7	111	21
   c	10	10	20
   d	15	0	15

5. Interpret compression limits

   Prefix-free coding minimizes weighted length among binary symbol codes for these frequencies, not every conceivable compression scheme. Decoder needs the code tree or codebook; transmitting that overhead may dominate short messages. Equal frequencies can yield different optimal codes, and one symbol may use an empty code only when the message length is otherwise known under a different convention.

This is a complete program. Compile with C++17 and enter the input described below.

#include<iostream>
#include<vector>
#include<string>
#include<queue>
#include<functional>
#include<array>
#include<utility>
struct Node{
    long long frequency;
    int left,right,symbol;
};
int main(){
    int k;
    std::cin>>k;
    std::vector<Node>nodes;
    std::array<long long,26>frequency{};
    std::priority_queue<std::pair<long long,int>,std::vector<std::pair<long long,int>>,
        std::greater<std::pair<long long,int>>>
        heap;
    for(int i=0;i<k;++i){
        char c;
        long long f;
        std::cin>>c>>f;
        frequency[c-'a']=f;
        nodes.push_back({f,-1,-1,c-'a'});
        heap.push({f,i});
    }
    while(heap.size()>1){
        auto a=heap.top();
        heap.pop();
        auto b=heap.top();
        heap.pop();
        int id=nodes.size();
        nodes.push_back({a.first+b.first,a.second,b.second,-1});
        heap.push({a.first+b.first,id});
    }
    std::array<std::string,26>codes;
    if(!heap.empty()){
        std::vector<std::pair<int,std::string>>stack{{heap.top().second,""}};
        while(!stack.empty()){
            auto[id,path]=stack.back();
            stack.pop_back();
            Node node=nodes[id];
            if(node.symbol>=0){
                codes[node.symbol]=
                    path.empty()?"0":path; // One symbol uses one bit by explicit convention.
            }
            else{
                stack.push_back({node.right,path+'1'});
                stack.push_back({node.left,path+'0'});
            }
        }
    }
    long long cost=0;
    for(int c=0;c<26;++c){
        if(frequency[c]){
            std::cout<<char('a'+c)<<' '<<codes[c]<<'\n';
            cost+=frequency[c]*codes[c].size();
        }
    }
    std::cout<<"COST "<<cost<<'\n';
}

Complexity analysis

O(k log k) tree construction, O(k) nodes. Emitting/storing strings costs O(L), where L is the sum of codeword lengths and can be O(k²) for a skewed tree; total O(k log k+L) time and O(k+L) space here. With k≤26 both are small. Frequencies and weighted cost fit long long.

Example input and output

Read k (0..26), then k distinct lowercase symbols and positive frequencies ≤10^9. Print symbol/code rows in alphabet order, followed by COST and weighted bit length. A singleton uses code 0; empty alphabet costs zero.

Input

4
a 5
b 7
c 10
d 15

Output

a 110
b 111
c 10
d 0
COST 71

The three merges create a tree with code lengths 3,3,2,1 and weighted cost 71.

Practical applications

Use for frequency-based prefix coding and recognizing weighted-depth objectives. Optimal merge computes the same objective for k≥2 without code reconstruction. Arithmetic/range coding and dictionary methods solve different compression models.

Check your understanding

Why is a leaf-path code prefix-free?

Put it into practice

Check every pair of printed codewords for a prefix relation and recompute weighted length.