Huffman Coding

DSA · Classic Algorithms

Theory

Huffman coding is a greedy algorithm for lossless data compression. Instead of giving every character the same number of bits (8 in ASCII), it gives frequent characters short codes and rare characters long codes. It counts how often each character appears, puts each character in a min-heap by frequency, and repeatedly removes the two least frequent nodes, merging them into a new node whose frequency is their sum. When one node remains, it is the root of a binary tree: walking left adds 0 and walking right adds 1, and each leaf's path is its code. Because no code is a prefix of another, the encoded bits can be decoded without separators. Huffman coding is used inside ZIP (DEFLATE), JPEG and MP3.

Why we use it

It produces the optimal prefix code for given symbol frequencies, reducing file sizes without losing information. It is also a standard example of a greedy algorithm combined with a heap.

When to use it

Use it when symbol frequencies are uneven, such as text or image data. If all symbols are equally likely, fixed-length codes are just as good.

How it works

  1. Count character frequencies
  2. Push each character into a min-heap
  3. Heap has more than 1 node? Yes: Pop two smallest, merge, push sum. No: Root of tree is ready.
  4. Left edge = 0, right edge = 1
  5. Leaf paths are the codes

Syntax

heap of (freq, node)
while len(heap) > 1:
    a, b = two smallest
    push (a.freq + b.freq, Node(a, b))
Time O(k log k) for k distinct symbols

Example

import heapq
from collections import Counter

text = "techtown teaches data"
freq = Counter(text)
heap = [[f, i, ch] for i, (ch, f) in enumerate(freq.items())]
heapq.heapify(heap)
counter = len(heap)
while len(heap) > 1:
    lo = heapq.heappop(heap)
    hi = heapq.heappop(heap)
    heapq.heappush(heap, [lo[0] + hi[0], counter, (lo, hi)])
    counter += 1

codes = {}
def assign(node, code=""):
    item = node[2]
    if isinstance(item, str):
        codes[item] = code or "0"
    else:
        assign(item[0], code + "0")
        assign(item[1], code + "1")
assign(heap[0])

for ch, code in sorted(codes.items(), key=lambda kv: (len(kv[1]), kv[0])):
    print(repr(ch), freq[ch], code)
encoded = "".join(codes[c] for c in text)
print("Original bits:", len(text) * 8, "| Huffman bits:", len(encoded))

decode = {v: k for k, v in codes.items()}
out, buf = [], ""
for bit in encoded:
    buf += bit
    if buf in decode:
        out.append(decode[buf]); buf = ""
print("Decoded:", "".join(out))

Key points

DSA topics

Introduction to DSA

Arrays and Searching

Sorting Algorithms

Linked Lists

Stacks and Queues

Hashing

Trees

Heaps

Graphs

Algorithm Techniques

Classic Algorithms

Dynamic Programming

T
Tech Town
Log InSign Up Free
Home SQL Python DSA Power BI Snowflake Databricks Spark Gen AI Practice Problems Contest Blog

Data Structures & Algorithms

The complete DSA roadmap: theory, why and when to use every structure and algorithm, Big O complexity, and Python code you can run right here in the browser.

{{ sectionCount }}
Sections
{{ topicCount }}
Topics
Free
Forever
Hands-on practice Practice DSA Online 251 problems across 13 patterns, with hidden tests and step-by-step optimal solutions. Start practising →
Section {{ sec.num }}

{{ sec.label }}

DSA  /  {{ current.sectionLabel }}  /  {{ current.name }}

{{ current.name }}

Theory

{{ current.def }}

Why we use it

{{ current.why }}

When to use it

{{ current.when }}

Flowchart — how {{ current.name }} works
{{ nd.text }}
{{ nd.text }}
◇ {{ nd.text }}
Yes → {{ nd.yes }}
No → {{ nd.no }}
Step-by-step visualisation
{{ cell.v }}
{{ cell.i }} {{ cell.tag }}
Step {{ vizStepLabel }}: {{ vizNote }}
■ comparing ■ swapping / moving ■ done / found ■ out of range
Complexity & Pseudocode
{{ current.syntax }}
Example Code
{{ current.example }}
▶ Try It Live — runs real Python 3 in your browser (first run loads the engine)
{{ liveOutput }}
{{ liveError }}
Key Points — click to check off as you learn
  • {{ pt.mark }} {{ pt.text }}

Share this topic