Use the priority queue to implement Huffman Tree, written in C++ and use STL.
#include <iostream>
#include <stdlib.h>
#include <queue>
#include <vector>
using namespace std;
struct Node
{
int val;
struct Node * left;
struct Node * right;
};
typedef struct Node * p_Node;
struct cmp
{
bool operator () (p_Node const &p1, p_Node const &p2)
{
return p1->val > p2->val;
}
};
p_Node createNode(int val, p_Node left, p_Node right)
{
p_Node node = (p_Node)malloc(sizeof(struct Node));
node->val = val;
node->left = left;
node->right = right;
return node;
}
p_Node buildTree(int * vec, int n)
{
priority_queue<p_Node, vector<p_Node>, cmp> forest;
for(int i = 0; i < n; i++)
{
p_Node node = createNode(vec[i], NULL, NULL);
forest.push(node);
}
while(forest.size() > 1)
{
p_Node node1 = forest.top();
forest.pop();
p_Node node2 = forest.top();
forest.pop();
cout<<node1->val<<" "<<node2->val<<endl;
p_Node new_node = createNode(node1->val + node2->val, node1, node2);
forest.push(new_node);
}
return forest.top();
}
