# Huffman Coding (Algorithm, Example and Time complexity)

This article contains basic concept of **Huffman coding with their algorithm, example of Huffman coding and time complexity** of a Huffman coding is also prescribed in this article.

Submitted by Abhishek Kataria, on June 23, 2018

## Huffman coding

- Huffman Algorithm was developed by David Huffman in 1951.
- This is a technique which is used in a data compression or it can be said that it is a coding technique which is used for encoding data.
- This technique is a mother of all data compression scheme.
- This idea is basically dependent upon the frequency, i.e. the frequency of the corresponding character which needs to be compressed, and by that frequency, only Huffman code will be generated.
- In case of Huffman coding, the most generated character will get the small code and least generated character will get the large code.
- Huffman tree is a specific method of representing each symbol.
- This technique produces a code in such a manner that no codeword is a prefix of some other code word. These codes are called as prefix code.

## Algorithm for Huffman code

1. Input:-Number of message with frequency count. 2. Output: - Huffman merge tree. 3. Begin 4. Let Q be the priority queue, 5. Q= {initialize priority queue with frequencies of all symbol or message} 6. Repeat n-1 times 7. Create a new node Z 8. X=extract_min(Q) 9. Y=extract_min(Q) 10. Frequency(Z) =Frequency(X) +Frequency(y); 11. Insert (Z, Q) 12. End repeat 13. Return (extract_min(Q)) 14. End.

**Example:**

Let obtain a set of Huffman code for the message **(m1.....m7)** with relative frequencies **(q1.....q7) = (4,5,7,8,10,12,20)**. Let us draw the Huffman tree for the given set of codes.

**Step 1) ** Arrange the data in ascending order in a table.

**4,5,7,8,10,12,20**

**Step 2)** Combine first two entries of a table and by this create a parent node.

**Step 3)**

**A)** Remove the entries 4 and 5 from the table and inert 9 at its appropriate position. **7,8,9,10,12,20**

Combine minimum value of table and create a parent node.

**B)** Now remove the entries 7 and 8 from the table and insert 15 at its appropriate position. **9,10,12,15,20**

Combine minimum value of two blocks and create a parent node.

**C)** Remove the entries 9 and 10 from the table and insert 19 at its proper position. **12,15,19,20.**

Combine minimum value of two blocks and create parent node.

**D)** Remove the entries 15 and 12 from the table and insert 27 at its appropriate position. **19,20,27**

Combine minimum value of two blocks and create parent node.

**E)** Remove the entries 19 and 20 from the table and insert 39 in the table. **27,39**

Combine minimum value of two blocks and create parent node.

**Step 4)** Now assign left child as 0 and right child as 1 to encode the frequencies.

**Now, codes for the given frequencies are given below:**

### Time complexity:

O(nlogn) is the overall time complexity. Where n is the number of characters.

Related Tutorials

- Introduction to Algorithms
- Introduction to Greedy Strategy in Algorithms
- Stability in sorting
- External Merge Sorting Algorithm
- Radix Sort and its Algorithm
- Bucket Sort Algorithm
- Bubble sort Algorithm, Flow Chart and C++ Code
- Insertion sort Algorithm, flowchart and C, C++ Code
- Merge Sort | One of the best sorting algorithms used for large inputs
- Binary Search in C, C++
- Randomized Binary Search
- Meta Binary Search | One-sided Binary Search
- Difference between Linear Search and Binary Search
- Binary Search in String
- Variants of Binary Search
- Sieve of Eratosthenes to find prime numbers
- Optimal Merge Pattern (Algorithm and Example)
- Given an array of n numbers, Check whether there is any duplicate or not
- Finding the missing number
- Find the number occurring an odd number of times
- Find the pair whose sum is closest to zero in minimum time complexity
- Find three elements in an array such that their sum is equal to given element K
- Bitonic Search Algorithm
- Check whether a number is Fibonacci or not
- Segregate even and odd numbers in minimum time complexity
- Find trailing zeros in factorial of a number
- Find Nearest Greatest Neighbours of each element in an array
- Interpolation search algorithm
- Floor and ceil of an element in an array using C++
- Two Elements whose sum is closest to zero
- Find a pair with a given difference
- Count number of occurrences (or frequency) in a sorted array
- Find a Fixed Point (Value equal to index) in a given array
- Find the maximum element in an array which is first increasing and then decreasing
- Dynamic Programming (Components, Applications and Elements)
- Algorithm for fractional knapsack problem
- Algorithm and procedure to solve a longest common subsequence problem
- Find the Nth Fibonacci number | C++
- Longest Common Subsequence using Dynamic programming (DP)
- Longest Increasing Subsequence using Dynamic programming (DP)
- Find the maximum sub-array sum using KADANE'S ALGORITHM
- Non-intersecting chords using Dynamic Programming (DP)
- Edit Distance using Dynamic Programming (DP)
- Finding Ugly Number using Dynamic Programming (DP)

- Backtracking (Types and Algorithms)
- 4 Queen's problem and solution using backtracking algorithm
- N Queen's problem and solution using backtracking algorithm
- Find the GCD (Greatest Common Divisor) of two numbers using EUCLID'S ALGORITHM
- Compute the value of A raise to the power B using Fast Exponentiation
- Implement First Come First Served (FCFS) CPU Scheduling Algorithm using C program
- Implementations of FCFS scheduling algorithm using C++
- Implementation of Shortest Job First (SJF) Non-Preemptive CPU scheduling algorithm using C++
- Implementation of Shortest Job First (SJF) Preemptive CPU scheduling algorithm using C++
- Implementation of Priority scheduling (Pre-emptive) algorithm using C++
- Implementation of Priority scheduling (Non Pre-emptive) algorithm using C++
- Implementation of Round Robin CPU Scheduling algorithm using C++
- Analysis of LRU page replacement algorithm and Belady's anomaly
- Branch and Bound
- Find the roots of a complex polynomial equation using Regula Falsi Method in C
- Divide and Conquer Paradigm (What it is, Its Applications, Pros and Cons)
- Strassen's Matrix Multiplication in algorithms
- Tournament Tree and their properties
- Deterministic and Non Deterministic Algorithms
- Lower Bound Theory
- Non Recursive Tree Traversal Algorithm
- Line Drawing Algorithm
- P and NP problems and solutions | Algorithms
- 2 – 3 Trees Algorithm
- Midpoint Circle Algorithm
- Reliability design problem
- Removing consecutive duplicates from a string
- Fast Exponentiation using Bitmasking
- Egg dropping problem using Dynamic Programming (DP)
- Wild card matching problem using Dynamic programming (DP)
- Compute sum of digits in all numbers from 1 to N for a given N
- Minimum jumps required using Dynamic programming (DP)
- Graph coloring problem's solution using backtracking algorithm
- Breadth First Search (BFS) and Depth First Search (DFS) Algorithms
- Travelling Salesman Problem
- Kruskal's (P) and Prim's (K) Algorithms
- Multistage graph problem with forward approach and backward approach algorithms
- Floyd Warshall algorithm with its Pseudo Code

Comments and Discussions!