Greedy Algorithms | Set 4 (Efficient Huffman Coding for Sorted Input) | GeeksforGeeks

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.

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);

}

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