Huffman Coding

import heapq

def huffman_codes(freq):
    # heap holds [weight, tie_id, node]; node is (symbol, left, right)
    heap = [[w, i, (sym, None, None)] for i, (sym, w) in enumerate(freq.items())]
    heapq.heapify(heap)
    tie = len(heap)
    while len(heap) > 1:
        w1, _, n1 = heapq.heappop(heap)
        w2, _, n2 = heapq.heappop(heap)
        heapq.heappush(heap, [w1 + w2, tie, (None, n1, n2)])
        tie += 1

    codes = {}
    def walk(node, path):
        sym, left, right = node
        if sym is not None:
            codes[sym] = path or "0"  # single-symbol edge case
            return
        walk(left, path + "0")
        walk(right, path + "1")

    walk(heap[0][2], "")
    return codes


print(huffman_codes({"a": 5, "b": 2, "c": 1, "d": 1}))
# {'a': '0', 'b': '10', 'c': '110', 'd': '111'}

type Node = { sym: string | null; left?: Node; right?: Node; w: number };

function huffmanCodes(freq: Record<string, number>): Record<string, string> {
  // simple array used as a heap via sort (fine for teaching-size inputs)
  let heap: Node[] = Object.entries(freq).map(([sym, w]) => ({ sym, w }));
  while (heap.length > 1) {
    heap.sort((a, b) => a.w - b.w);
    const n1 = heap.shift()!;
    const n2 = heap.shift()!;
    heap.push({ sym: null, left: n1, right: n2, w: n1.w + n2.w });
  }

  const codes: Record<string, string> = {};
  const walk = (node: Node, path: string): void => {
    if (node.sym !== null) {
      codes[node.sym] = path || "0";
      return;
    }
    walk(node.left!, path + "0");
    walk(node.right!, path + "1");
  };
  walk(heap[0], "");
  return codes;
}

console.log(huffmanCodes({ a: 5, b: 2, c: 1, d: 1 }));
// { a: '0', b: '10', c: '110', d: '111' }

import java.util.*;

class Huffman {
    static class Node {
        Character sym; int w; Node left, right;
        Node(Character sym, int w) { this.sym = sym; this.w = w; }
    }

    static void walk(Node n, String path, Map<Character, String> out) {
        if (n.sym != null) { out.put(n.sym, path.isEmpty() ? "0" : path); return; }
        walk(n.left, path + "0", out);
        walk(n.right, path + "1", out);
    }

    static Map<Character, String> huffmanCodes(Map<Character, Integer> freq) {
        PriorityQueue<Node> pq = new PriorityQueue<>((a, b) -> a.w - b.w);
        for (var e : freq.entrySet()) pq.add(new Node(e.getKey(), e.getValue()));
        while (pq.size() > 1) {
            Node a = pq.poll(), b = pq.poll();
            Node parent = new Node(null, a.w + b.w);
            parent.left = a; parent.right = b;
            pq.add(parent);
        }
        Map<Character, String> codes = new HashMap<>();
        walk(pq.poll(), "", codes);
        return codes;
    }

    public static void main(String[] args) {
        Map<Character, Integer> freq =
            Map.of('a', 5, 'b', 2, 'c', 1, 'd', 1);
        System.out.println(huffmanCodes(freq));
    }
}

#include <stdio.h>
#include <stdlib.h>

typedef struct Node {
    char sym; int w;
    struct Node *left, *right;
} Node;

Node *make(char sym, int w, Node *l, Node *r) {
    Node *n = malloc(sizeof(Node));
    n->sym = sym; n->w = w; n->left = l; n->right = r;
    return n;
}

/* find index of smallest-weight node in a simple array pool */
int min_index(Node **pool, int n) {
    int m = 0;
    for (int i = 1; i < n; i++)
        if (pool[i]->w < pool[m]->w) m = i;
    return m;
}

void walk(Node *n, char *path, int depth) {
    if (!n->left && !n->right) {
        path[depth] = '\0';
        printf("%c=%s\n", n->sym, depth ? path : "0");
        return;
    }
    path[depth] = '0'; walk(n->left, path, depth + 1);
    path[depth] = '1'; walk(n->right, path, depth + 1);
}

int main(void) {
    char syms[] = {'a', 'b', 'c', 'd'};
    int  freq[] = {5, 2, 1, 1};
    int  n = 4;
    Node *pool[8];
    for (int i = 0; i < n; i++) pool[i] = make(syms[i], freq[i], NULL, NULL);

    int size = n;
    while (size > 1) {
        int i = min_index(pool, size); Node *a = pool[i]; pool[i] = pool[--size];
        int j = min_index(pool, size); Node *b = pool[j]; pool[j] = pool[--size];
        pool[size++] = make('\0', a->w + b->w, a, b);
    }
    char path[16];
    walk(pool[0], path, 0);
    return 0;
}

#include <iostream>
#include <queue>
#include <string>
#include <vector>
#include <map>

struct Node {
    char sym; int w;
    Node *left = nullptr, *right = nullptr;
    Node(char s, int weight) : sym(s), w(weight) {}
};

struct Cmp {
    bool operator()(Node *a, Node *b) const { return a->w > b->w; }
};

void walk(Node *n, const std::string &path, std::map<char, std::string> &out) {
    if (!n->left && !n->right) { out[n->sym] = path.empty() ? "0" : path; return; }
    walk(n->left, path + "0", out);
    walk(n->right, path + "1", out);
}

int main() {
    std::vector<std::pair<char, int>> freq = {{'a', 5}, {'b', 2}, {'c', 1}, {'d', 1}};
    std::priority_queue<Node *, std::vector<Node *>, Cmp> pq;
    for (auto &[s, w] : freq) pq.push(new Node(s, w));

    while (pq.size() > 1) {
        Node *a = pq.top(); pq.pop();
        Node *b = pq.top(); pq.pop();
        Node *parent = new Node('\0', a->w + b->w);
        parent->left = a; parent->right = b;
        pq.push(parent);
    }
    std::map<char, std::string> codes;
    walk(pq.top(), "", codes);
    for (auto &[s, code] : codes) std::cout << s << "=" << code << "\n";
    return 0;
}