2 of 14

HUFFMAN TREES

Mukti -

Team Nexus

Objectives :

Define Huffman Tree and Huffman Coding
Understand why prefix codes matter
Preview the construction process

3 of 14

Construction of Huffman Tree

Start with symbols as individual nodes

Repeatedly combine two smallest-weight nodes

New node weight = sum of children’s weights

Continue until one tree remains

(Include a step-by-step diagram)

4 of 14

PROPERTIES OF HUFFMAN TREE

Minimizes sum of (frequency × code-length) for all symbols

Yields optimal prefix code (no codeword is a prefix of another)

5 of 14

FILE COMPRESSION

▶ Lossless Compression:

▶ ZIP, GZIP, PNG use Huffman coding

▶ Lossy Compression:

▶ JPEG (images) and MP3 (audio) apply Huffman coding on quantized data

6 of 14

FAX MACHINE COMPRESSION

▶ Uses Modified Huffman coding

▶ Combines run-length encoding with Huffman coding

▶ Efficiently compresses black-and-white scan lines

7 of 14

ADAPTIVE HUFFMAN CODING

▶ Allows on-the-fly tree updates

▶ Applied to streaming or anomaly-detection scenarios

▶ Example: audio anomaly detection under concept drift

8 of 14

DEFINITION OF HEAP

A heap is a tree-based data structure

Heap property:

Max-heap: Each parent's key ≥ its children's keys

Min-heap: Each parent's key ≤ its children's keys

9 of 14

SHAPE PROPERTY

Typically a complete binary tree
Stored in an array:
Space efficient
Implicit parent/child indexing

10 of 14

OPERATIONS

Build-heap (heapify): O(n)
Insert (push): O(log n)
Extract-max/min (pop): O(log n)
Peek (find-max/min): O(1)

11 of 14

PRIORITY QUEUES

Applications:

Task scheduling

Event simulation

Interrupt handling

12 of 14

HEAPSORT

In-place sorting algorithm
Time complexity: O(n log n)
Uses heap for priority queue operations

Heaps enhance graph algorithms
Dijkstra’s shortest-path:

Min-heap to extract closest unvisited vertex

Prim’s minimum-spanning-tree:

Heap for edge selection

13 of 14

GRAPH ALGORITHMS

Heaps enhance graph algorithms
Dijkstra’s shortest-path:

Min-heap to extract closest unvisited vertex

Prim’s minimum-spanning-tree:

Heap for edge selection

14 of 14

Criterion	Huffman Tree	Heap
Primary purpose	Static, optimal prefix‑code construction for lossless compression	Dynamic priority queue supporting repeated insertions/removals
Key operations	Build once in O(n log n); encode/decode by tree traversal	Build in O(n); insert/extract in O(log n); peek in O(1)
Use cases	File and data compression (ZIP, PNG, JPEG, GZIP, codecs), neural‑net pruning	Task scheduling, event simulation, Dijkstra/Prim, heapsort, k‑way merge
Memory structure	Full binary tree of 2n–1 nodes (for n symbols)	Complete binary tree, stored as array of n elements
Dynamic vs. static	Generally static once built; tree structure fixed for a data set	Dynamic: supports ongoing inserts/removals
When better	Huffman tree: when needing optimal static coding for known symbol frequencies; compressing data permanently.	Heap: when requiring dynamic priority operations, frequent insert/extract; scheduling or streaming contexts.