If we know that the given array is sorted (by non-decreasing order of frequency), we can generate Huffman codes in O(n) time. Following is a O(n) algorithm for sorted input.
1. Create two empty queues.
2. Create a leaf node for each unique character and Enqueue it to the first queue in non-decreasing order of frequency. Initially second queue is empty.
3. Dequeue two nodes with the minimum frequency by examining the front of both queues. Repeat following steps two times
…..a) If second queue is empty, dequeue from first queue.
…..b) If first queue is empty, dequeue from second queue.
…..c) Else, compare the front of two queues and dequeue the minimum.
4. Create a new internal node with frequency equal to the sum of the two nodes frequencies. Make the first Dequeued node as its left child and the second Dequeued node as right child. Enqueue this node to second queue.
5. Repeat steps#3 and #4 until there is more than one node in the queues. The remaining node is the root node and the tree is complete.
Also read http://plg.uwaterloo.ca/~ftp/dmc/huffman.txt
Read full article from Greedy Algorithms | Set 4 (Efficient Huffman Coding for Sorted Input) | GeeksforGeeks
1. Create two empty queues.
2. Create a leaf node for each unique character and Enqueue it to the first queue in non-decreasing order of frequency. Initially second queue is empty.
3. Dequeue two nodes with the minimum frequency by examining the front of both queues. Repeat following steps two times
…..a) If second queue is empty, dequeue from first queue.
…..b) If first queue is empty, dequeue from second queue.
…..c) Else, compare the front of two queues and dequeue the minimum.
4. Create a new internal node with frequency equal to the sum of the two nodes frequencies. Make the first Dequeued node as its left child and the second Dequeued node as right child. Enqueue this node to second queue.
5. Repeat steps#3 and #4 until there is more than one node in the queues. The remaining node is the root node and the tree is complete.
struct
QueueNode* buildHuffmanTree(
char
data[],
int
freq[],
int
size)
{
struct
QueueNode *left, *right, *top;
// Step 1: Create two empty queues
struct
Queue* firstQueue = createQueue(size);
struct
Queue* secondQueue = createQueue(size);
// Step 2:Create a leaf node for each unique character and Enqueue it to
// the first queue in non-decreasing order of frequency. Initially second
// queue is empty
for
(
int
i = 0; i < size; ++i)
enQueue(firstQueue, newNode(data[i], freq[i]));
// Run while Queues contain more than one node. Finally, first queue will
// be empty and second queue will contain only one node
while
(!(isEmpty(firstQueue) && isSizeOne(secondQueue)))
{
// Step 3: Dequeue two nodes with the minimum frequency by examining
// the front of both queues
left = findMin(firstQueue, secondQueue);
right = findMin(firstQueue, secondQueue);
// Step 4: Create a new internal node with frequency equal to the sum
// of the two nodes frequencies. Enqueue this node to second queue.
top = newNode(
'$'
, left->freq + right->freq);
top->left = left;
top->right = right;
enQueue(secondQueue, top);
}
return
deQueue(secondQueue);
}
struct
QueueNode* findMin(
struct
Queue* firstQueue,
struct
Queue* secondQueue)
{
// Step 3.a: If second queue is empty, dequeue from first queue
if
(isEmpty(firstQueue))
return
deQueue(secondQueue);
// Step 3.b: If first queue is empty, dequeue from second queue
if
(isEmpty(secondQueue))
return
deQueue(firstQueue);
// Step 3.c: Else, compare the front of two queues and dequeue minimum
if
(getFront(firstQueue)->freq < getFront(secondQueue)->freq)
return
deQueue(firstQueue);
return
deQueue(secondQueue);
}
Read full article from Greedy Algorithms | Set 4 (Efficient Huffman Coding for Sorted Input) | GeeksforGeeks