美文网首页
Huffman Tree (use priority queue

Huffman Tree (use priority queue

作者: pangolulu | 来源:发表于2016-04-17 17:29 被阅读153次

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

    相关文章

      网友评论

          本文标题:Huffman Tree (use priority queue

          本文链接:https://www.haomeiwen.com/subject/lebolttx.html