CS 112 : Data Structures
Sesh Venugopal
Huffman Tree Building Algorithm: Running Time Analysis
Basic Operations to Count
1. Enqueue in Symbols queue: O(1) per enqueue
Symbols queue
pfrsate
2. Dequeue from Symbols queue: O(1) per dequeue
3. Build a subtree out of two other subtrees: O(1) per build
Root node probability = 0.05 (p) + 0.05 (f)
4. Enqueue in Trees queue: O(1) per enqueue
Trees queue
0.1
pf
Sesh Venugopal
CS 112: Huffman Analysis 2
Basic Operations to Count
(a) Compare the probability of front of symbols queue, with that of the front of trees queue
5. Compare probabilities: O(1) per comparison
Symbols queue
0.1
Trees queue
pf
Dequeue the lesser of the two. Here, since they are both 0.1, either can be dequeued (pick arbitrarily). Say we pick r from the symbols queue, and dequeue it
rsate
0.1
Sesh Venugopal CS 112: Huffman Analysis 3
Basic Operations to Count
pfrsate
0.05 0.05 0.1 0.15 0.2 0.2 0.25
(b) Compare the probability of front of symbols queue, with that of the front of trees queue
Symbols queue
r 0.15s a t e Trees queue
pf
6. Dequeue from Trees queue: O(1) per dequeue
Dequeue the lesser of the two. Here, the trees queue front has a smaller probability, so it will be dequeued
0.1
Sesh Venugopal CS 112: Huffman Analysis 4
Basic Operations to Count
1. Enqueue in Symbols queue: O(1) per enqueue
2. Dequeue from Symbols queue: O(1) per dequeue
3. Build a subtree out of two other subtrees: O(1) per build 4. Enqueue in Trees queue: O(1) per enqueue
5. Compare probabilities: O(1) per comparison
6. Dequeue from Trees queue: O(1) per dequeue
Assuming n symbols, we need big O worst case running time to build a Huffman tree for n symbols
Sesh Venugopal CS 112: Huffman Analysis 5
Basic Operations to Count
Suppose there are k subtrees
1. Enqueue in Symbols queue: O(1) per enqueue * n = O(n)
2. Dequeue from Symbols queue: O(1) per dequeue * n = O(n)
3. Build a subtree out of two other subtrees: O(1) per build * k = O(k) 4. Enqueue in Trees queue: O(1) per enqueue * k = O(k)
5. Compare probabilities: O(1) per comparison* ??
6. Dequeue from Trees queue: O(1) per dequeue * k = O(k)
“Order Arithmetic”: O(n)*O(m) = O(m*n)
Sesh Venugopal CS 112: Huffman Analysis 6
How many probability comparisons?
1.0
Nothing in Symbols queue
0.6
0.35 e e against s-a sa
t against p-f-r, e against p-f-r
r against p-f-r, s against p-f-r
0.4
r
pf
t
0.2 Nothing in 0.1
Trees queue
s against p-f-r, a against p-f-r
– For any Huffman tree, the first subtree will require 0 comparisons.
– Any other subtree except final (top) will require AT MOST 2 comparisons.
– The final subtree here requires 0 comparisons, but it’s possible that it requires 1 comparison in other cases (if last subtree is made out of last symbol in Symbols queue and single subtree in Trees queue)
Sesh Venugopal CS 112: Huffman Analysis 7
0
2
2
2
1
Basic Operations to Count
The number of probability comparisons for any subtree build for any Huffman tree is a constant (0,1,2).
And the time per probability comparison is O(1) .
So time for all probability comparisons for any subtree is O(1)
1. Enqueue in Symbols queue: O(1) per enqueue * n = O(n)
2. Dequeue from Symbols queue: O(1) per dequeue * n = O(n)
3. Build a subtree out of two other subtrees: O(1) per build * k = O(k) 4. Enqueue in Trees queue: O(1) per enqueue * k = O(k)
5. Compare probabilities: O(1) per subtree * k = O(k)
6. Dequeue from Trees queue: O(1) per dequeue * k = O(k)
Sesh Venugopal CS 112: Huffman Analysis 8
What is value of k – how many subtrees?
Alternative 1
1.0
01
0 0.4 1 0.6 01
0.2 t 0.35 e 0101
Alternative 2
1.0
0
0.6
1
0.4
0101
0.35 e t a 01
s
01
00.11 pf
0 0.11 pf
r
sa
0.2
r
These trees (alternatives for the same set of symbols) have very different shapes, but the number of subtrees (including final) is the same = 6!
Sesh Venugopal CS 112: Huffman Analysis 9
What is value of k – how many subtrees?
Huffman tree is a special kind of binary tree in which every node has either 0 children or 2 children – this is called a strictly binary tree (in other words no node has exactly 1 child)
Theorem: If a strictly binary tree has n leaf nodes, then it has n-1 non-leaf (internal) nodes
Which means for a Huffman tree built for n symbols, so n leaf nodes, there are exactly n-1 subtrees (subtree roots are the internal nodes). In other words, k = n-1 (for our example, n=7 and k=6)
Sesh Venugopal CS 112: Huffman Analysis 10
Total Running Time Substitute n-1 for k
1. Enqueue in Symbols queue: O(1) per enqueue * n = O(n)
2. Dequeue from Symbols queue: O(1) per dequeue * n = O(n)
3. Build a subtree out of two other subtrees: O(1) per build * k = O(1) * (n-1) = O(n) 4. Enqueue in Trees queue: O(1) per enqueue * k = O(k) = O(n)
5. Compare probabilities: O(1) per comparison * k = O(k) = O(n)
6. Dequeue from Trees queue: O(1) per dequeue * k = O(k) = O(n)
Worst case running time to build a Huffman tree for
n symbols is O(n)
Sesh Venugopal CS 112: Huffman Analysis 11