排序输入的有效霍夫曼编码
在以前的霍夫曼编码问题中，频率未排序。如果按排序顺序给出频率列表，则分配代码的任务将更加高效。
在这个问题中，我们将使用两个空队列。然后为每个唯一字符创建一个叶子节点，并将其以频率递增的顺序插入队列。
在这种方法中，算法的复杂度为O(n)。
输入输出
Input:
Different letters and their frequency in sorted order
Letters: {L, K, X, C, E, B, A, F}
Frequency: {1, 1, 2, 2, 2, 2, 3, 4}
Output:
Codes for the letters
L: 0000
K: 0001
X: 001
C: 010
E: 011
F: 10
B: 110
A: 111算法
huffmanCodes(dataList,freqList,n)
输入：数据列表和频率列表，以及列表中的数据数量n。
输出-分配给代码的字符。
Begin root := huffmanTree(dataList, freqList, n) //create root of Huffman tree create an array to store codes, and top pointer for that array. call getCodes(root, array, top) to find codes for each character. End
getCodes（root：node，array，top）
输入：根节点，存储代码的数组，数组的顶部。
输出-每个字符的代码
Begin
if leftChild(root) ≠φ then
array[top] := 0
getCodes(leftChild(root), array, top)
if rightChild(root) ≠φ then
array[top] = 1
getCode(rightChild(root), array, top)
if leftChild(root) = φ AND rightChild(root) = φ then
display the character ch of root
for all entries of the array do
display the code in array[i] for character ch
done
EndhuffmanTree(dataList,freqList,n)
输入-数据列表和频率列表，以及列表n中的数据数量。
输出-创建霍夫曼树
Begin
for all different character ch do
add node with ch and frequency of ch into queue q1
done
while q1 is not empty OR size of q2 ≠ 1 do
find two minimum node using q1 and q2 and add them as left and
right child of a new node.
add new node in q2
done
delete node from q2 and return that node.
End示例
#include<iostream>
#include<queue>
using namespace std;
struct node {
char data;
int freq;
node *child0, *child1;
};
node *getNode(char d, int f) {
node *newNode = new node;
newNode->data = d;
newNode->freq = f;
newNode->child0 = NULL;
newNode->child1 = NULL;
return newNode;
}
node *findMinNode(queue<node*>&q1, queue<node*>&q2) {
node *minNode;
if(q1.empty()) { //if first queue is empty, delete and return node from second queue
minNode = q2.front();
q2.pop();
return minNode;
}
if(q2.empty()) { //if second queue is empty, delete and return node from first queue
minNode = q1.front();
q1.pop();
return minNode;
}
if((q1.front()->freq) < (q2.front()->freq)) { //find smaller from two queues
minNode = q1.front();
q1.pop();
return minNode;
}else {
minNode = q2.front();
q2.pop();
return minNode;
}
}
node *huffmanTree(char data[], int frequency[], int n) {
node *c0, *c1, *par;
node *newNode;
queue<node*> qu1, qu2;
for(int i = 0; i<n; i++) { //add all node to queue 1
newNode = getNode(data[i], frequency[i]);
qu1.push(newNode);
}
while(!(qu1.empty() && (qu2.size() == 1))) {
c0 = findMinNode(qu1, qu2); //find two minimum as two child
c1 = findMinNode(qu1, qu2);
node *newNode = getNode('#', c0->freq+c1->freq);
//中间节点具有特殊字符
par = newNode;
par->child0 = c0;
par->child1 = c1;
qu2.push(par); //add sub tree into queue 2
}
node *retNode = qu2.front();
qu2.pop();
return retNode;
}
void getCodes(node *rootNode, int array[], int n) { //array to store the code
if(rootNode->child0 != NULL) {
array[n] = 0;
getCodes(rootNode->child0, array, n+1);
}
if(rootNode->child1 != NULL) {
array[n] = 1;
getCodes(rootNode->child1, array, n+1);
}
if(rootNode->child0 == NULL && rootNode->child1 == NULL) { // when root is leaf node
cout << rootNode->data << ": ";
for(int i = 0; i<n; i++)
cout << array[i];
cout << endl;
}
}
void huffmanCodes(char data[], int frequency[], int n) {
node *rootNode = huffmanTree(data, frequency, n);
int array[50], top = 0;
getCodes(rootNode, array, top);
}
int main() {
char data[] = {'L', 'K', 'X', 'C', 'E', 'B', 'A', 'F'};
int frequency[] = {1, 1, 2, 2, 2, 2, 3, 4};
int n = sizeof(data)/sizeof(data[0]);
huffmanCodes(data, frequency, n);
}输出结果
L: 0000 K: 0001 X: 001 C: 010 E: 011 F: 10 B: 110 A: 111