1. Huffman tree, optimal binary tree, the smallest binary tree of WPL
Weighted path length (WPL):
Assume that the binary tree has n leaf nodes, each leaf node has a weight wk, and the length from the root node to each leaf node is lk , then the sum of the weighted path lengths of each leaf node WPL
Characteristics of Huffman tree:
1. There is no node with degree 1;
2. The left and right subtrees of any non-leaf node of the Huffman tree are still Huffman trees after exchange;
3. A Huffman tree with n leaf nodeshas a total of 2n-1 nodes (inferred from the fact that there are no nodes with degree 1, n0 + n1 + n2 = 2*n0-1);
4. For the same set of weights {w1, w2, …, wn}, there are two Huffman trees with isomorphism;
5. The number of external nodes is one more than the number of internal nodes;
2. Two characteristics of heap
Structural: a complete binary tree represented by an array;
Ordering: The key of any node is the maximum value (or minimum value) of all nodes in its subtree
(There is no relationship between the child nodes of the heap nodes)
1. Heap operation
1 typedef struct HNode *Heap; /* Heap type definition */
2 struct HNode {
3 ElementType *Data; /* Array to store elements */
4 int Size; /* The current number of elements in the heap */
5 int Capacity; /* Maximum capacity of the heap */
6};
7 typedef Heap MaxHeap; /* maximum heap */
8 typedef Heap MinHeap; /* Minimum heap */
9
10 #define MAXDATA 1000 /* This value should be defined as a value greater than all possible elements in the heap */
11
12 MaxHeap CreateHeap( int MaxSize )
13 { /* Create an empty maximum heap with a capacity of MaxSize */
14
15 MaxHeap H = (MaxHeap)malloc(sizeof(struct HNode));
16 H->Data = (ElementType *)malloc((MaxSize + 1)*sizeof(ElementType));
17 H->Size = 0;
18 H->Capacity = MaxSize;
19 H->Data[0] = MAXDATA; /* Define "sentinel" as a value greater than all possible elements in the heap*/
20
21 return H;
twenty two }
twenty three
24 boolIsFull(MaxHeapH)
25 {
26 return (H->Size == H->Capacity);
27}
28
29 bool Insert( MaxHeap H, ElementType X )
30 { /* Insert element X into maximum heap H, where H->Data[0] has been defined as a sentinel */
31 int i;
32
33 if ( IsFull(H) ) {
34 printf("Maximum heap is full");
35 return false;
36}
37 i = + + H->Size; /* i points to the position of the last element in the heap after insertion */
38 for ( ; H->Data[i/2] < X; i/=2 )
39 H->Data[i] = H->Data[i/2]; /* Filter up X */
40 H->Data[i] = X; /* Insert X */
41 return true;
42 }
43
44 #define ERROR -1 /* The error identifier should be defined as an element value that cannot appear in the heap according to the specific situation */
45
46 boolIsEmpty(MaxHeapH)
47 {
48 return (H->Size == 0);
49 }
50
51 ElementType DeleteMax(MaxHeapH)
52 { /* Remove the element with the largest key value from the maximum heap H and delete a node */
53 int Parent, Child;
54 ElementType MaxItem, X;
55
56 if ( IsEmpty(H) ) {
57 printf("The maximum heap is empty");
58 return ERROR;
59 }
60
61 MaxItem = H->Data[1]; /* Get the maximum value stored in the root node */
62 /* Use the last element in the max heap to filter the lower nodes upward starting from the root node */
63 X = H->Data[H->Size--]; /* Note that the current heap size should be reduced */
64 for( Parent=1; Parent*2<=H->Size; Parent=Child ) {
65 Child = Parent * 2;
66 if( (Child!=H->Size) & amp; & amp; (H->Data[Child]<H->Data[Child + 1]) )
67 Child + + ; /* Child points to the larger of the left and right child nodes */
68 if( X >= H->Data[Child] ) break; /* Found the right location */
69 else /* Lower filter X */
70 H->Data[Parent] = H->Data[Child];
71 }
72 H->Data[Parent] = X;
73
74 returnMaxItem;
75 }
76
77 /*---------- Build the largest heap -----------*/
78 void PercDown( MaxHeap H, int p )
79 { /* Lower filtering: adjust the sub-heap in H with H->Data[p] as the root to the maximum heap */
80 int Parent, Child;
81ElementTypeX;
82
83 X = H->Data[p]; /* Get the value stored in the root node */
84 for( Parent=p; Parent*2<=H->Size; Parent=Child ) {
85 Child = Parent * 2;
86 if( (Child!=H->Size) & amp; & amp; (H->Data[Child]<H->Data[Child + 1]) )
87 Child + + ; /* Child points to the larger of the left and right child nodes */
88 if( X >= H->Data[Child] ) break; /* Found the right location */
89 else /* Lower filter X */
90 H->Data[Parent] = H->Data[Child];
91 }
92 H->Data[Parent] = X;
93}
94
95 void BuildHeap(MaxHeapH)
96 { /* Adjust the elements in H->Data[] to meet the orderliness of the maximum heap */
97 /* It is assumed here that all H->Size elements already exist in H->Data[] */
98
99 int i;
100
101 /* Starting from the parent node of the last node to root node 1 */
102 for( i = H->Size/2; i>0; i-- )
103 PercDown(H, i);
104}
Heap operations, c code
2. Heap operation examples
The path of the heap, inserting a given sequence of numbers into an initially empty small top heap H[].
Then for any given index `i`, print the path from H[i] to the root node.
1 #include <stdio.h>
2 /* 1. Define heap H */
3 #defineMAXN 1001
4 #define MINH -10001
5 int H[MAXN], size;//Heap, size of heap
6 /* 2. Heap initialization */
7 voidCreate()
8 {
9 size = 0;
10 H[0] = MINH;/*Set "sentry"*/
11 }
12 /* 3. Heap insertion */
13 void Insert (int X)
14 {
15 /* Omit checking whether the heap is full */
16 int i; //46 23 26 24 10
17/*
18 The subscripts start from 1 and are inserted one by one.
19 Insertion process, from back to front, compare with its parent node one by one
20 The parent node is large, filter X
21 1 2 3 4 5
22 46 <-46 1/2==0 0
23 23 46 <-23 2/2==1 1 0
24 23 46 26 <-26 3/2==1 1 0
25 23 24 26 46 <-24 4/2==2 2 1 0
26 10 23 26 46 24 <-10 5/2==2 2 1 0
27 */
28 for (i= + + size; H[i/2] > X; i/=2)
29 H[i] = H[i/2];
30 H[i] = X; //Insert X into H
31}
32
33 int main()
34 {
35/*
36 Read n and m
37 Build a heap based on the input sequence
38 For m requirements: print path to root
39 5 3
40 46 23 26 24 10
41 5 4 3
42 */
43 int n, m, x, i, j;
44 scanf("%d%d", & amp;n, & amp;m);
45 Create(); /* Heap initialization */
46 for (i=0; i<n; i + + ) {
47 scanf("%d", & amp;x);
48 Insert(x); /*Build a heap by inserting one by one */
49 }
50
51 /* for(int i=1; i<=n; + + i)
52 printf("=",H[i]); */
53
54 /* m nodes */
55 for (i=0; i<m; i + + )
56 {
57 scanf("%d", & amp;j);//specific node
58 printf("%d", H[j]);
59 /*Output each node in the root direction*/
60 while (j>1) {
61 j /= 2;
62 printf(" %d", H[j]);
63}
64 printf("\
");
65 }
66 return 0;
67}
Minimum heap, insert and build heap
3. C++ creates a Huffman tree based on the given weight (using priority queue, greedy algorithm, Qingdao University mooc)
Xueyou code
#include <iostream>
#include <map>
#include<algorithm>
#include <queue>
#defineMAX500
using namespace std;
int n;
//Type of nodes in Huffman tree
struct HuffmanTree
{
char data;
int weight;
int parent, lchild, rchild;
};
HuffmanTree HT[MAX];
//y priority queue node type
struct NodeType
{
int now;//corresponds to the position in the Huffman tree (array subscript)
char data;
int weight;
bool operator<(const NodeType & amp; s) const//(small top heap)
{
return s.weight < weight;
}
};
priority_queue<NodeType> qu;
void CreateHuffmanTree()
{
NodeType e, e1, e2;
cout << "Please enter the elements of the constructed Huffman tree and the corresponding weights:" << endl;
for (int i = 0; i < n; i + + )
{
cin >> HT[i].data >> HT[i].weight;
}
//Add n nodes into the queue
for(int i=0;i<n;i + + )
{
e.now = i;
e.data = HT[i].data;
e.weight = HT[i].weight;
qu.push(e);
}
//Initialize the pointer field of the node
for (int i = 0; i < 2*n-1; i + + )
{
HT[i].parent = HT[i].lchild = HT[i].rchild = -1;
}
//Construct the remaining nodes of the huffman tree (the nodes obtained by summing)
for(int j=n;j<2*n-1;j + + )
{
e1 = qu.top();//Minimum access
qu.pop();
e2 = qu.top();//Access to the second smallest
qu.pop();
HT[j].weight = e1.weight + e2.weight;
HT[j].lchild = e1.now;
HT[j].rchild = e2.now;
HT[e1.now].parent = j;//The parent of the smallest node is the node at position n
HT[e2.now].parent = j;//The second smallest one is also
e.now = j;//Construct new node
e.weight = e1.weight + e2.weight;
qu.push(e);
}
}
void HuffmmanCode()
{
string code;
for(int i=0;i<n;i + + )
{
code = "";
int curnow = i;
int f = HT[curnow].parent;//If the parent of the current node is not the root node, look up (until you reach the root node, you can get the reverse order of Huffman coding)
while(f!=-1)//The constructed huffman tree has only the root node and no parent, so the parent of the root node is -1
{
if (HT[f].lchild == curnow)
code + = '0';
else
code + = '1';
curnow = f;
f = HT[curnow].parent;
}
cout << HT[i].data << " ";
reverse(code.begin(), code.end() );
cout << code << endl;
}
}
int main()
{
cout << "Please enter the number of elements to build the Huffman tree:";
freopen("d:\1.txt","r",stdin );
cin >> n;
CreateHuffmanTree();
cout << "Huffman encoding is:" << endl;
HuffmmanCode();
return 0;
}
View Code
Modify Qingdao University code
#include <iostream>
#include <vector>
#include <queue>
#include <map>
using namespace std;
struct Node{
char ch;
int data;
Node* left;
Node* right;
Node(){ left = right= NULL;}
Node(char ch, int data):ch(ch),data(data){
left = right = NULL;
}
};
struct HuffmanTree{
Node* root;
HuffmanTree(){root = NULL;}
HuffmanTree(char ch, int weight){
root = new Node(ch,weight);
}
HuffmanTree(vector<HuffmanTree> & amp;nodes){
priority_queue<HuffmanTree, vector<HuffmanTree>,
greater<HuffmanTree>> q(nodes.begin(),nodes.end());
HuffmanTree tmp;
for(int i=1; i<nodes.size(); + + i){
tmp.root = new Node();
tmp.root->left = q.top().root; q.pop();
tmp.root->right = q.top().root; q.pop();
tmp.root->data = tmp.root->left->data + tmp.root->right->data;
q.push(tmp);
}
root = q.top().root;
}
bool operator > (const HuffmanTree & amp;t) const{
return this->root->data > t.root->data;
}
void print(){
rprint(root,0);
}
void rprint(Node* r, int depth){
for(int i=0; i<depth; + + i) cout<<" ";
if(!r) cout<<"[/]"<<endl;
else{
cout<<r->data<<endl;
rprint(r->left, depth + 1);
rprint(r->right,depth + 1);
}
}
//huffman encoding
map<string, char>HuffmanCode;
void createHuffmanCode(Node* root, string tmp){
if(root->left==NULL & amp; & amp; root->right==NULL ){
HuffmanCode[tmp] = root->ch;
return;
}
createHuffmanCode(root->left, tmp + ="0");
tmp.pop_back();
createHuffmanCode(root->right, tmp + ="1");
tmp.pop_back();
}
//Print code
void printHuffmanCode(){
string tmp;
createHuffmanCode(root,tmp);
map<char, string>t;
for(map<string, char >::iterator it = HuffmanCode.begin();
it != HuffmanCode.end(); + + it )
t[it->second] = it->first;
for(map<char, string >::iterator it = t.begin();
it != t.end(); + + it )
cout << it->first << " " << it->second << endl;
}
};
int main()
{
freopen("d:\1.txt","r",stdin );
int nv,weight;
char ch;
cin>>nv;
vector<HuffmanTree> nodes;
for(int i=0; i<nv; + + i){
cin >> ch >> weight;
nodes.emplace_back(ch,weight);
}
HuffmanTree ht(nodes);
//ht.print();
ht.printHuffmanCode();
return 0;
}
View Code
Qingdao University code
#include <iostream>
#include <vector>
#include <queue>
using namespace std;
struct Node{
int data;
Node* left;
Node* right;
Node(){ left = right= NULL;}
Node(int data){
this->data = data;
left = right = NULL;
}
};
struct HuffmanTree{
Node* root;
HuffmanTree(){root = NULL;}
HuffmanTree(int weight){
root = new Node(weight);
}
HuffmanTree(vector<HuffmanTree> & amp;nodes){
priority_queue<HuffmanTree, vector<HuffmanTree>,
greater<HuffmanTree>> q(nodes.begin(),nodes.end());
HuffmanTree tmp;
for(int i=1; i<nodes.size(); + + i){
tmp.root = new Node();
tmp.root->left = q.top().root; q.pop();
tmp.root->right = q.top().root; q.pop();
tmp.root->data = tmp.root->left->data + tmp.root->right->data;
q.push(tmp);
}
root = q.top().root;
}
bool operator > (const HuffmanTree & amp;t) const{
return this->root->data > t.root->data;
}
void print(){
rprint(root,0);
}
void rprint(Node* r, int depth){
for(int i=0; i<depth; + + i) cout<<" ";
if(!r) cout<<"[/]"<<endl;
else{
cout<<r->data<<endl;
rprint(r->left, depth + 1);
rprint(r->right,depth + 1);
}
}
};
int main()
{
int nv,weight;
cin>>nv;
vector<HuffmanTree> nodes;
for(int i=0; i<nv; + + i){
cin>>weight;
nodes.emplace_back(weight);
}
HuffmanTree ht(nodes);
ht.print();
return 0;
}
/*
7
10 15 12 3 4 13 1
*/
View Code