精华内容
下载资源
问答
  • 优先队列学习之哈弗曼树
    2017-08-03 22:46:00

    转载自:http://www.cppblog.com/darren/archive/2009/06/09/87224.html

    priority_queue 调用 STL里面的 make_heap(), pop_heap(), push_heap() 算法
    实现,也算是堆的另外一种形式。

    先写一个用 STL 里面堆算法实现的与真正的STL里面的 priority_queue  用法相
    似的 priority_queue, 以加深对 priority_queue 的理解

    #include <iostream>
    #include <algorithm>
    #include <vector>
    
    using namespace std;
    
    class priority_queue
    {
        private:
            vector<int> data;
            
        public:
            void push( int t ){ 
                data.push_back(t); 
                push_heap( data.begin(), data.end()); 
            }
            
            void pop(){
                pop_heap( data.begin(), data.end() );
                data.pop_back();
            }
            
            int top()    { return data.front(); }
            int size()   { return data.size();  }
            bool empty() { return data.empty(); }
    };
    
    
    int main()
    {
        priority_queue  test;
        test.push( 3 );
        test.push( 5 );
        test.push( 2 );
        test.push( 4 );
        
        while( !test.empty() ){
            cout << test.top() << endl;
            test.pop(); }
            
        return 0;
    }

     

    STL里面的 priority_queue 写法与此相似,只是增加了模板及相关的迭代器什么的。


    priority_queue 对于基本类型的使用方法相对简单。
    他的模板声明带有三个参数,priority_queue<Type, Container, Functional>
    Type 为数据类型, Container 为保存数据的容器,Functional 为元素比较方式。
    Container 必须是用数组实现的容器,比如 vector, deque 但不能用 list.
    STL里面默认用的是 vector. 比较方式默认用 operator< , 所以如果你把后面俩个
    参数缺省的话,优先队列就是大顶堆,队头元素最大。
    看例子

     

    #include <iostream>
    #include <queue>
    
    using namespace std;
    
    int main(){
        priority_queue<int> q;
        
        for( int i= 0; i< 10; ++i ) q.push( rand() );
        while( !q.empty() ){
            cout << q.top() << endl;
            q.pop();
        }
        
        getchar();
        return 0;
    }

     


    如果要用到小顶堆,则一般要把模板的三个参数都带进去。
    STL里面定义了一个仿函数 greater<>,对于基本类型可以用这个仿函数声明小顶堆
    例子:

    #include <iostream>
    #include <queue>
    
    using namespace std;
    
    int main(){
        priority_queue<int, vector<int>, greater<int> > q;
        
        for( int i= 0; i< 10; ++i ) q.push( rand() );
        while( !q.empty() ){
            cout << q.top() << endl;
            q.pop();
        }
        
        getchar();
        return 0;
    }

     


     对于自定义类型,则必须自己重载 operator< 或者自己写仿函数
    先看看例子:

    #include <iostream>
    #include <queue>
    
    using namespace std;
    
    struct Node{
        int x, y;
        Node( int a= 0, int b= 0 ):
            x(a), y(b) {}
    };
    
    bool operator<( Node a, Node b ){
        if( a.x== b.x ) return a.y> b.y;
        return a.x> b.x; 
    }
    
    int main(){
        priority_queue<Node> q;
        
        for( int i= 0; i< 10; ++i )
        q.push( Node( rand(), rand() ) );
        
        while( !q.empty() ){
            cout << q.top().x << ' ' << q.top().y << endl;
            q.pop();
        }
        
        getchar();
        return 0;
    }

     


    自定义类型重载 operator< 后,声明对象时就可以只带一个模板参数。
    但此时不能像基本类型这样声明
    priority_queue<Node, vector<Node>, greater<Node> >;
    原因是 greater<Node> 没有定义,如果想用这种方法定义
    则可以按如下方式

    例子:

    #include <iostream>
    #include <queue>
    
    using namespace std;
    
    struct Node{
        int x, y;
        Node( int a= 0, int b= 0 ):
            x(a), y(b) {}
    };
    
    struct cmp{
        bool operator() ( Node a, Node b ){
            if( a.x== b.x ) return a.y> b.y;
            
            return a.x> b.x; }
    };
    
    int main(){
        priority_queue<Node, vector<Node>, cmp> q;
        
        for( int i= 0; i< 10; ++i )
        q.push( Node( rand(), rand() ) );
        
        while( !q.empty() ){
            cout << q.top().x << ' ' << q.top().y << endl;
            q.pop();
        }
        
        getchar();
        return 0;
    }

    --------------------------------------

    如下转载自:http://blog.csdn.net/zhc_ac/article/details/47395399

    题目描述

     在一个果园里,多多已经将所有的果子打了下来,而且按果子的不同种类分成了不同的堆。多多决定把所有的果子合成一堆。
    每一次合并,多多可以把两堆果子合并到一起,消耗的体力等于两堆果子的重量之和。可以看出,所有的果子经过n-1次合并之后,就只剩下一堆了。多多在合并果子时总共消耗的体力等于每次合并所消耗体力之和。
    因为还要花大力气把这些果子搬回家,所以多多在合并果子时要尽可能地节省体力。假定每个果子重量都为1,并且已知果子的种类数和每种果子的数目,你的任务是设计出合并的次序方案,使多多耗费的体力最少,并输出这个最小的体力耗费值。
    例如有3种果子,数目依次为1,2,9。可以先将1、2堆合并,新堆数目为3,耗费体力为3。接着,将新堆与原先的第三堆合并,又得到新的堆,数目为12,耗费体力为12。所以多多总共耗费体力=3+12=15。可以证明15为最小的体力耗费值。
     

    输入

     第一行是一个整数n(1<=n<=10000),表示果子的种类数。第二行包含n个整数,用空格分隔,第i个ai(1<=ai<=20000)是第i个果子的数目。
     

    输出

     输出包括一行,这一行只包含一个整数,也就是最小的体力耗费值。输入数据保证这个值小于2^31。
     

    示例输入

    3
    1 2 9

    示例输出

    15

     

    #include <iostream>
    #include <stdio.h>
    #include <string.h>
    #include <queue>//头文件
    
    using namespace std;
    
    struct cmp//函数从小到大排序,因为默认的优先队列是从大到小排序
    {
        bool operator ()(long long &a,long long &b)
        {
            return a>b;
        }
    };
    
    int main()
    {
        priority_queue<long long ,vector<long long>,cmp>q;//优先队列定义方式
    
        long long  a;
        int n,i;
    
        while(scanf("%d",&n)!=EOF)
        {
            long long  x=0,y=0;
            long long  ans = 0,sum = 0;
    
            for(i=0;i<n;i++)
            {
                scanf("%lld",&a);
                q.push(a);//把a加入到优先队列q中
            }
            while(!q.empty())//当队列里还有数存在时
            {
                x = q.top();//从队列中取出
                q.pop();//把队列中的第一个字符删除
                if(!q.empty())
                {
                       y = q.top();
                       q.pop();
                        ans = x+y;
                        sum = sum + ans;
                        q.push(ans);
                }
            }
            printf("%lld\n",sum);
        }
        return 0;
    }

     

     

    转载于:https://www.cnblogs.com/hellowooorld/p/7282516.html

    更多相关内容
  • 构建哈弗曼树 C/C++

    2020-07-06 14:50:42
    什么是哈弗曼树? 给定N个权值作为N个叶子结点,构造一棵二叉树,若该的带权路径长度达到最小,称这样的二叉树为最优二叉树,也称为哈夫曼。哈夫曼是带权路径长度最短的,权值较大的结点离根较近。 权值:...

    什么是哈弗曼树?

    给定N个权值作为N个叶子结点,构造一棵二叉树,若该树的带权路径长度达到最小,称这样的二叉树为最优二叉树,也称为哈夫曼树。哈夫曼树是带权路径长度最短的树,权值较大的结点离根较近。

    权值:树的每个节点数据域data可以放一个特定的数来代表它的值,可以叫做权值。

    路径:在一棵树中,从一个结点往下可以达到的孩子或孙子结点之间的通路,称为路径。也就是经过的节点。

    路径长度:路径通路中分支的数目称为路径长度。也就是边的条数。

    带权路径长度:从根结点到该结点之间的路径长度与该结点的权的乘积。

    树的带权路径长度:所有叶子结点的带权路径长度之和,记为WPL。

    怎么构建哈弗曼树?

    哈弗曼树就是带权路径长度最小的二叉树,那么意味着权重越大的叶子结点离根节点的路径长度越短。

    若要将前面那颗二叉树转换成一棵二叉树,应该是这样:

    它们同一层的各个节点权重也可以换位置,同样构成哈弗曼树。

    构造步骤:

    一、根据权重构造节点。创建一个保持升序的队列。

    二、将带权重节点压入队列中

    三、弹出队首前两个节点,节点的权重是最小和次小。将这两个节点权重相加构成一个新权重,再用新权重构造一个新节点。将新节点作为这两个节点的根节点,构造成一棵二叉树,并将根节点压入队列中:(队列保持升序)

    四、重复步骤三,再次弹出队首两个节点,权重为最小和次小。同样将两个的权重相加,得到一个新权重,构造一个新节点,新构造的节点作为根节点。构成一棵新的二叉树。

    五、重复步骤四,得到如下这棵树,将根节点插入队列中,得到队列中仅有一个节点。

    六、弹出队列中唯一这个节点,这个节点就是这棵哈夫曼树的根节点。就可以得到如下这棵哈弗曼树。

     

    队列一定是任何时候都保持升序,可以利用C++的优先队列:priority_queue

    但是按照节点权重进行升序,需要自定义比较方法。

    说得比较粗糙,完全自己笔记。见谅。

    看下实现代码:

    #include<iostream>
    #include<vector>
    #include<queue>
    #include<functional>
    using namespace std;
    
    //哈弗曼树节点和权重比较方法,优先队列会使用这个权重比较方法
    typedef struct HuffmanNode
    {
    	int weight;
    	struct HuffmanNode *lChild;  //左节点
    	struct HuffmanNode *rChild;  //右节点
    	//重写()作为队列比较函数
    	bool operator()(struct HuffmanNode*nodeA, struct HuffmanNode *nodeB)
    	{
    		return nodeA->weight > nodeB->weight;
    	}
    }HuffNode;
    
    
    
    //构建哈夫曼树
    HuffNode * createHuffmanTree(vector<int> weight)
    {
    	//优先队列
    	priority_queue<HuffmanNode*,vector<HuffmanNode*>,HuffNode > huffQue;
    
    	//按照权重构造节点,并将节点插入队列中
    	for (vector<int>::iterator it = weight.begin(); it != weight.end(); it++)
    	{
    		HuffNode *node = new HuffNode;
    		node->weight = *it;
    		node->lChild = NULL;
    		node->rChild = NULL;
    		huffQue.push(node);
    	}
    
    	//将权重最小和次小的节点弹出,将两个节点的权重相加,作为构造新节点的权重
    	//将这个新节点作为根节点,权重最小的节点作为左孩子,次小的作为右孩子。
    	//将新的根节点插入队列中
    	while (huffQue.size() > 1)
    	{
    		HuffNode *lChild = huffQue.top();
    		huffQue.pop();
    		HuffNode *rChild = huffQue.top();
    		huffQue.pop();
    
    		HuffmanNode *parent = new HuffmanNode;
    		parent->lChild = lChild;
    		parent->rChild = rChild;
    		parent->weight = lChild->weight + rChild->weight;
    		huffQue.push(parent);
    	}
    
    	//弹出队列中最后一个节点,作为哈弗曼树的根节点
    	HuffmanNode *root = huffQue.top();
    	return root;
    }
    
    //先序遍历哈弗曼树
    void preOrder(HuffmanNode *root)
    {
    	if (NULL == root)
    	{
    		return;
    	}
    
    	cout << root->weight<<" ";
    	preOrder(root->lChild);
    	preOrder(root->rChild);
    }
    
    void freeHuffManTree(HuffNode* root)
    {
    	if (NULL == root)
    	{
    		return;
    	}
    
    	freeHuffManTree(root->lChild);
    	freeHuffManTree(root->rChild);
    	free(root);
    	root = NULL;
    }
    
    int main()
    {
    	vector<int> weight = { 4,5,10,15,20};
    
    	//构造哈夫曼树
    	HuffmanNode *root = createHuffmanTree(weight);
    
    	//前序遍历哈弗曼树
    	cout << "哈弗曼树的前序遍历结果为:" << endl;
    	preOrder(root);
    	cout << endl;
    
    	freeHuffManTree(root);
    
    	system("pause");
    	return 0;
    }

    输出结果:

    顺序与前面得到的哈弗曼树先序遍历结果一致。

    展开全文
  • 哈夫曼的基本构建与操作

    万次阅读 多人点赞 2016-11-29 20:02:32
    看到的讲解huffman的一篇比较好懂的博客,唯一不足的地方就是代码里面使用Malloc时没有强制类型转换。。。。 出处:http://blog.csdn.net/wtfmonking/article/details/17150499# 1、基本概念 a、路径和路径长度 ...

    看到的讲解huffman树的一篇比较好懂的博客

    出处:http://blog.csdn.net/wtfmonking/article/details/17150499#

    1、基本概念


    a、路径和路径长度

    若在一棵树中存在着一个结点序列 k1,k2,……,kj, 使得 kiki+1 的双亲(1<=i<j),则称此结点序列是从 k1 到 kj 的路径。

    从 k1 到 kj 所经过的分支数称为这两点之间的路径长度,它等于路径上的结点数减1.


    b、结点的权和带权路径长度

    在许多应用中,常常将树中的结点赋予一个有着某种意义的实数,我们称此实数为该结点的权,(如下面一个树中的蓝色数字表示结点的权)

    结点的带权路径长度规定为从树根结点到该结点之间的路径长度与该结点上权的乘积。


    c、树的带权路径长度

    树的带权路径长度定义为树中所有叶子结点的带权路径长度之和,公式为:


    其中,n表示叶子结点的数目,wi 和 li 分别表示叶子结点 ki 的权值和树根结点到 ki 之间的路径长度。

    如下图中树的带权路径长度 WPL = 9 x 2 + 12 x 2 + 15 x 2 + 6 x 3 + 3 x 4 + 5 x 4  =  122



    d、哈夫曼树

    哈夫曼树又称最优二叉树。它是 n 个带权叶子结点构成的所有二叉树中,带权路径长度 WPL 最小的二叉树。

    如下图为一哈夫曼树示意图。


    2、构造哈夫曼树


    假设有n个权值,则构造出的哈夫曼树有n个叶子结点。 n个权值分别设为 w1、w2、…、wn,则哈夫曼树的构造规则为:


    (1) 将w1、w2、…,wn看成是有n 棵树的森林(每棵树仅有一个结点);


    (2) 在森林中选出两个根结点的权值最小的树合并,作为一棵新树的左、右子树,且新树的根结点权值为其左、右子树根结点权值之和;


    (3)从森林中删除选取的两棵树,并将新树加入森林;


    (4)重复(2)、(3)步,直到森林中只剩一棵树为止,该树即为所求得的哈夫曼树。


     如:对 下图中的六个带权叶子结点来构造一棵哈夫曼树,步骤如下:


    注意:为了使得到的哈夫曼树的结构尽量唯一,通常规定生成的哈夫曼树中每个结点的左子树根结点的权小于等于右子树根结点的权。


    具体算法如下:

    1. //2、根据数组 a 中 n 个权值建立一棵哈夫曼树,返回树根指针  
    2. struct BTreeNode* CreateHuffman(ElemType a[], int n)  
    3. {  
    4.     int i, j;  
    5.     struct BTreeNode **b, *q;  
    6.     b = malloc(n*sizeof(struct BTreeNode));  
    7.     for (i = 0; i < n; i++) //初始化b指针数组,使每个指针元素指向a数组中对应的元素结点  
    8.     {  
    9.         b[i] = malloc(sizeof(struct BTreeNode));  
    10.         b[i]->data = a[i];  
    11.         b[i]->left = b[i]->right = NULL;  
    12.     }  
    13.     for (i = 1; i < n; i++)//进行 n-1 次循环建立哈夫曼树  
    14.     {  
    15.         //k1表示森林中具有最小权值的树根结点的下标,k2为次最小的下标  
    16.         int k1 = -1, k2;  
    17.         for (j = 0; j < n; j++)//让k1初始指向森林中第一棵树,k2指向第二棵  
    18.         {  
    19.             if (b[j] != NULL && k1 == -1)  
    20.             {  
    21.                 k1 = j;  
    22.                 continue;  
    23.             }  
    24.             if (b[j] != NULL)  
    25.             {  
    26.                 k2 = j;  
    27.                 break;  
    28.             }  
    29.         }  
    30.         for (j = k2; j < n; j++)//从当前森林中求出最小权值树和次最小  
    31.         {  
    32.             if (b[j] != NULL)  
    33.             {  
    34.                 if (b[j]->data < b[k1]->data)  
    35.                 {  
    36.                     k2 = k1;  
    37.                     k1 = j;  
    38.                 }  
    39.                 else if (b[j]->data < b[k2]->data)  
    40.                     k2 = j;  
    41.             }  
    42.         }  
    43.         //由最小权值树和次最小权值树建立一棵新树,q指向树根结点  
    44.         q = malloc(sizeof(struct BTreeNode));  
    45.         q->data = b[k1]->data + b[k2]->data;  
    46.         q->left = b[k1];  
    47.         q->right = b[k2];  
    48.   
    49.         b[k1] = q;//将指向新树的指针赋给b指针数组中k1位置  
    50.         b[k2] = NULL;//k2位置为空  
    51.     }  
    52.     free(b); //删除动态建立的数组b  
    53.     return q; //返回整个哈夫曼树的树根指针  
    54. }  

    3、哈夫曼编码

    在电报通信中,电文是以二进制的0、1序列传送的,每个字符对应一个二进制编码,为了缩短电文的总长度,采用不等长编码方式,构造哈夫曼树,

    将每个字符的出现频率作为字符结点的权值赋予叶子结点,每个分支结点的左右分支分别用0和1编码,从树根结点到每个叶子结点的路径上

    所经分支的0、1编码序列等于该叶子结点的二进制编码。如上文所示的哈夫曼编码如下:

    a 的编码为:00

    b 的编码为:01

    c 的编码为:100

    d 的编码为:1010

    e 的编码为:1011

    f 的编码为:11


    4、哈夫曼树的操作运算


    以上文的哈夫曼树作为具体实例,用详细的程序展示哈夫曼树的操作运算

    1. #include<stdio.h>  
    2. #include<stdlib.h>  
    3. typedef int ElemType;  
    4. struct BTreeNode  
    5. {  
    6.     ElemType data;  
    7.     struct BTreeNode* left;  
    8.     struct BTreeNode* right;  
    9. };  
    10.   
    11. //1、输出二叉树,可在前序遍历的基础上修改。采用广义表格式,元素类型为int  
    12. void PrintBTree_int(struct BTreeNode* BT)  
    13. {  
    14.     if (BT != NULL)  
    15.     {  
    16.         printf("%d", BT->data); //输出根结点的值  
    17.         if (BT->left != NULL || BT->right != NULL)  
    18.         {  
    19.             printf("(");  
    20.             PrintBTree_int(BT->left); //输出左子树  
    21.             if (BT->right != NULL)  
    22.                 printf(",");  
    23.             PrintBTree_int(BT->right); //输出右子树  
    24.             printf(")");  
    25.         }  
    26.     }  
    27. }  
    28.   
    29. //2、根据数组 a 中 n 个权值建立一棵哈夫曼树,返回树根指针  
    30. struct BTreeNode* CreateHuffman(ElemType a[], int n)  
    31. {  
    32.     int i, j;  
    33.     struct BTreeNode **b, *q;  
    34.     b = malloc(n*sizeof(struct BTreeNode));  
    35.     for (i = 0; i < n; i++) //初始化b指针数组,使每个指针元素指向a数组中对应的元素结点  
    36.     {  
    37.         b[i] = malloc(sizeof(struct BTreeNode));  
    38.         b[i]->data = a[i];  
    39.         b[i]->left = b[i]->right = NULL;  
    40.     }  
    41.     for (i = 1; i < n; i++)//进行 n-1 次循环建立哈夫曼树  
    42.     {  
    43.         //k1表示森林中具有最小权值的树根结点的下标,k2为次最小的下标  
    44.         int k1 = -1, k2;  
    45.         for (j = 0; j < n; j++)//让k1初始指向森林中第一棵树,k2指向第二棵  
    46.         {  
    47.             if (b[j] != NULL && k1 == -1)  
    48.             {  
    49.                 k1 = j;  
    50.                 continue;  
    51.             }  
    52.             if (b[j] != NULL)  
    53.             {  
    54.                 k2 = j;  
    55.                 break;  
    56.             }  
    57.         }  
    58.         for (j = k2; j < n; j++)//从当前森林中求出最小权值树和次最小  
    59.         {  
    60.             if (b[j] != NULL)  
    61.             {  
    62.                 if (b[j]->data < b[k1]->data)  
    63.                 {  
    64.                     k2 = k1;  
    65.                     k1 = j;  
    66.                 }  
    67.                 else if (b[j]->data < b[k2]->data)  
    68.                     k2 = j;  
    69.             }  
    70.         }  
    71.         //由最小权值树和次最小权值树建立一棵新树,q指向树根结点  
    72.         q = malloc(sizeof(struct BTreeNode));  
    73.         q->data = b[k1]->data + b[k2]->data;  
    74.         q->left = b[k1];  
    75.         q->right = b[k2];  
    76.   
    77.         b[k1] = q;//将指向新树的指针赋给b指针数组中k1位置  
    78.         b[k2] = NULL;//k2位置为空  
    79.     }  
    80.     free(b); //删除动态建立的数组b  
    81.     return q; //返回整个哈夫曼树的树根指针  
    82. }  
    83.   
    84. //3、求哈夫曼树的带权路径长度  
    85. ElemType WeightPathLength(struct BTreeNode* FBT, int len)//len初始为0  
    86. {  
    87.     if (FBT == NULL) //空树返回0  
    88.         return 0;  
    89.     else  
    90.     {  
    91.         if (FBT->left == NULL && FBT->right == NULL)//访问到叶子结点  
    92.             return FBT->data * len;  
    93.         else //访问到非叶子结点,进行递归调用,返回左右子树的带权路径长度之和,len递增  
    94.             return WeightPathLength(FBT->left,len+1)+WeightPathLength(FBT->right,len+1);  
    95.     }  
    96. }  
    97.   
    98. //4、哈夫曼编码(可以根据哈夫曼树带权路径长度的算法基础上进行修改)  
    99. void HuffManCoding(struct BTreeNode* FBT, int len)//len初始值为0  
    100. {  
    101.     static int a[10];//定义静态数组a,保存每个叶子的编码,数组长度至少是树深度减一  
    102.     if (FBT != NULL)//访问到叶子结点时输出其保存在数组a中的0和1序列编码  
    103.     {  
    104.         if (FBT->left == NULL && FBT->right == NULL)  
    105.         {  
    106.             int i;  
    107.             printf("结点权值为%d的编码:", FBT->data);  
    108.             for (i = 0; i < len; i++)  
    109.                 printf("%d", a[i]);  
    110.             printf("\n");  
    111.         }  
    112.         else//访问到非叶子结点时分别向左右子树递归调用,并把分支上的0、1编码保存到数组a  
    113.         {   //的对应元素中,向下深入一层时len值增1  
    114.             a[len] = 0;  
    115.             HuffManCoding(FBT->left, len + 1);  
    116.             a[len] = 1;  
    117.             HuffManCoding(FBT->right, len + 1);  
    118.         }  
    119.     }  
    120. }  
    121.   
    122. //主函数  
    123. void main()  
    124. {  
    125.     int n, i;  
    126.     ElemType* a;  
    127.     struct BTreeNode* fbt;  
    128.     printf("从键盘输入待构造的哈夫曼树中带权叶子结点数n:");  
    129.     while(1)  
    130.     {  
    131.         scanf("%d", &n);  
    132.         if (n > 1)  
    133.             break;  
    134.         else  
    135.             printf("重输n值:");  
    136.     }  
    137.     a = malloc(n*sizeof(ElemType));  
    138.     printf("从键盘输入%d个整数作为权值:", n);  
    139.     for (i = 0; i < n; i++)  
    140.         scanf(" %d", &a[i]);  
    141.     fbt = CreateHuffman(a, n);  
    142.     printf("广义表形式的哈夫曼树:");  
    143.     PrintBTree_int(fbt);  
    144.     printf("\n");  
    145.     printf("哈夫曼树的带权路径长度:");  
    146.     printf("%d\n", WeightPathLength(fbt, 0));  
    147.     printf("树中每个叶子结点的哈夫曼编码:\n");  
    148.     HuffManCoding(fbt, 0);  
    149. }  

    运行结果:

    展开全文
  • 哈弗曼树

    2018-01-23 11:55:40
    在介绍哈弗曼树之前先来看几个简单的概念: 在一个二叉树中: 定义一个从A结点到B结点所经过的分支序列为从A结点到B结点的路径。 定义从A结点到B结点所经过的分支个数为从A结点到B结点的路径长度。 从二叉树的根...

    在介绍哈弗曼树之前先来看几个简单的概念:
    在一个二叉树中:
    定义一个从A结点到B结点所经过的分支序列为从A结点到B结点的路径。
    定义从A结点到B结点所经过的分支个数为从A结点到B结点的路径长度。
    从二叉树的根节点到二叉树中所有节点的路径长度之和为该二叉树的路径长度。
    这里写图片描述
    Huffman树:带权路径长度最短的树称为哈夫曼树。
    Huffman树的创建:(用小堆来保存二叉树森林中的树)如int array[]={5,3,2,7}。
    1.先进行排序:升序排列为{2,3,5,7}。
    2.选出最小的两个数,先进行建树。这里写图片描述
    3.将新的二叉树放入二叉树森林中。
    这里写图片描述
    4.继续步骤2和3。
    这里写图片描述

    下面为构建Huffman树的算法:
    1.创建以权值为根的二叉树森林——>小堆
    2.构建(直到二叉树森林中只剩一棵树)
    1>.取权值最小的树pLeft,—–删除其。
    2>.取权值最小的树pRight,—–删除其。
    3>.pLeft的权值与pRight的权值作为其双亲,创建新树,将新树佳人苑二叉树森林中。

    3.比较左右子树权值的大小,决定放在左子树还是右子树。

    具体的代码实现如下:

    #include<iostream>
    #include<vector>
    using namespace std;
    template<class T>
    class Heap
    {
    public:
        Heap()
        {}
        Heap(const T*array, size_t size)//堆的创建
        {
            //1.将数组中的元素存起来
            _array.resize(size);
            for (size_t i = 0; i < size; i++)
            {
                _array[i] = array[i];
            }
            //2.向下调整
            int root = (size - 2) >> 1;
            for (; root >= 0; root--)
            {
                _AdjustDown(root);
            }
        }
        void Push(const T& data)
        {
            _array.push_back(data);
            if (_array.size() > 1)
            {
                _AdjustUp(_array.size() - 1);
            }
        }
        void Pop()
        {
            if (Size() == 0)
                return;
            else
            {
                size_t last = _array.size() - 1;
                swap(_array[0], _array[last]);
                _array.pop_back();
                //2.向下调整
                _AdjustDown(0);
            }
        }
        T Top()const
        {
            return _array[0];
        }
        bool Empty()const
        {
            return _array.empty();
        }
        size_t Size()const
        {
            return  _array.size();
        }
    private:
        void _AdjustDown(size_t parent)//向下调整
        {
            size_t child = parent * 2 + 1;
            size_t size = _array.size();
            while (child < size)
            {
                if ((child + 1 < size) && (_array[child] > _array[child + 1]))
                {
                    child += 1;
                }
                if (_array[parent]>_array[child])
                {
                    swap(_array[parent], _array[child]);
                    parent = child;
                    child = parent * 2 + 1;//继续走到其左侧,进行调整
                }
                else
                {
                    break;
                }
            }
        }
        void _AdjustUp(size_t child)//向上调整
        {
            size_t size = _array.size();
            size_t parent = (size - 2) >> 1;
            while (child > 0)
            {
                if (_array[parent] > _array[child])
                {
                    swap(_array[parent], _array[child]);
                    child = parent;
                    parent = (child - 1) >> 1;
                }
                else
                {
                    break;
                }
            }
        }
    private:
        vector<T>_array;
    };
    template<class W>
    struct HuffmanTreeNode
    {
        HuffmanTreeNode()
        : _pLeft(NULL)
        , _pRight(NULL)
        , _weight(0)
        {}
        HuffmanTreeNode(W weight)
        :_pLeft(NULL)
        , _pRight(NULL)
        , _weight(weight)
        {}
        HuffmanTreeNode<W>*_pLeft;
        HuffmanTreeNode<W>*_pRight;
        W _weight;//权值
    };
    template<class W>
    class HuffmanTree
    {
    public:
        typedef HuffmanTreeNode<W> Node;
        typedef Node* pNode;
        HuffmanTree()
            :_pRoot(NULL)
        {}
        HuffmanTree( W*array, size_t size, const W&invalid)
        {
            _CreatHuffmanTree(array, size, invalid);
        }
        ~HuffmanTree()
        {
            _Destroy(_pRoot);
        }
    private:
        void _CreatHuffmanTree(W*array, size_t size, const W&invalid)
        {
            if (hp.Empty())
            {
                _pRoot = NULL;
            }
            Heap<pNode>hp;//堆中存的是节点
            for (size_t i = 0; i<size; i++)
            {
                if (array[i] != invalid)
                {
                    hp.Push(new Node(array[i]));
                }
            }
            while (hp.Size()> 1)
            {
                //取堆顶元素
                pNode pLeft = hp.Top();
                hp.Pop();
                pNode pRight = hp.Top();
                hp.Pop();
                pNode parent = new Node(pLeft->_weight + pRight->_weight);//左右权值相加
                if (pLeft->_weight < pRight->_weight)
                {
                    parent->_pLeft = pLeft;
                    parent->_pRight = pRight;
                }
                else
                {
                    parent->_pLeft = pRight;
                    parent->_pRight = pLeft;
                }
                hp.Push(parent);
            }
            _pRoot = hp.Top();
        }
        void _Destory(pNode &pRoot)
        {
            if (pRoot)
            {
                _Destory(pRoot->_pLeft);
                _Destory(pRoot->_pRight);
                delete pRoot;
            }
        }
        pNode _pRoot;
        Heap<W> hp;
    };
    int main()
    {
        int array[] = { 5, 3, 2, 7 };
        HuffmanTree<int>h(array, 4, 0);
        system("pause");
        return 0;
    }

    仿函数的形式写法为:

    #include<iostream>
    #include<vector>
    using namespace std;
    template<class T>
    struct Greater
    {
        bool operator()(const T&a, const T&b)
        {
            return a > b;
        }
    };
    template<class T>
    struct Smaller
    {
        bool operator()(const T&a, const T&b)
        {
            return a < b;
        }
    };
    template<class T, class compare = Smaller<T>>
    class Heap
    {
    public:
        Heap()
        {}
        Heap(T*array, int size)//堆的创建
        {
            //1.将数组中的元素存起来
            _array.resize(size);
            for (int i = 0; i < size; i++)
            {
                _array[i] = array[i];
            }
            //2.向下调整
            int root = (size - 2) >> 1;
            for (; root >= 0; root--)
            {
                _AdjustDown(root);
            }
        }
        void Push(const T& data)
        {
            _array.push_back(data);
            if (_array.size() > 1)
            {
                _AdjustUp(_array.size() - 1);
            }
        }
        void Pop()
        {
            if (Size() == 0)
                return;
            else
            {
                int last = _array.size() - 1;
                swap(_array[0], _array[last]);
                _array.pop_back();
                //2.向下调整
                _AdjustDown(0);
            }
        }
        T Top()const
        {
            return _array[0];
        }
        bool Empty()const
        {
            return _array.empty();
        }
        size_t Size()const
        {
            return  _array.size();
        }
    private:
        void _AdjustDown(int parent)//向下调整
        {
            int child = parent * 2 + 1;
            int size = _array.size();
            while (child < size)
            {
                if ((child + 1 < size) && (compare()(_array[child], _array[child + 1])))
                {
                    child += 1;
                }
                if (compare()(_array[parent], _array[child]))
                {
                    swap(_array[parent], _array[child]);
                    parent = child;
                    child = parent * 2 + 1;//继续走到其左侧,进行调整
                }
                else
                    return;
            }
        }
        void _AdjustUp(int child)//向上调整
        {
            int size = _array.size();
            int parent = (size - 2) >> 1;
            while (child > 0)
            {
                if (compare()(_array[parent], _array[child]))
                {
                    swap(_array[parent], _array[child]);
                    child = parent;
                    parent = (child - 1) >> 1;
                }
                else
                {
                    break;
                }
            }
        }
    private:
        vector<T>_array;
    };
    template<class W>
    struct HuffmanTreeNode
    {
        HuffmanTreeNode()
        : _pLeft(NULL)
        , _pRight(NULL)
        , _weight(0)
        {}
        HuffmanTreeNode(W weight)
        :_pLeft(NULL)
        , _pRight(NULL)
        , _weight(weight)
        {}
        HuffmanTreeNode<W>*_pLeft;
        HuffmanTreeNode<W>*_pRight;
        W _weight;//权值
    };
    template<class W>
    class HuffmanTree
    {
    public:
        typedef HuffmanTreeNode<W> Node;
        typedef Node* pNode;
        HuffmanTree()
            :_pRoot(NULL)
        {}
        HuffmanTree( W*array, size_t size, const W&invalid)
        {
            _CreatHuffmanTree(array, size, invalid);
        }
        ~HuffmanTree()
        {
            _Destroy(_pRoot);
        }
    private:
        void _CreatHuffmanTree(W*array, size_t size, const W&invalid)
        {
            struct compare
            {                                          
                bool operator()(pNode pLeft, pNode Pright)
                {
                    return pLeft->_weight < Pright->_weight;
                }
            };
            Heap<pNode, compare>hp;//堆中存的是节点
            for (size_t i = 0; i<size; i++)
            {
                if (array[i] != invalid)
                {
                    hp.Push(new Node(array[i]));
                }
            }
            if (hp.Empty())
            {
                _pRoot = NULL;
            }
            while (hp.Size()> 1)
            {
                //取堆顶元素
                pNode pLeft = hp.Top();
                hp.Pop();
                pNode pRight = hp.Top();
                hp.Pop();
                pNode parent = new Node(pLeft->_weight + pRight->_weight);//左右权值相加
                hp.Push(parent);
            }
            _pRoot = hp.Top();
        }
        void _Destory(pNode &pRoot)
        {
            if (pRoot)
            {
                _Destory(pRoot->_pLeft);
                _Destory(pRoot->_pRight);
                delete pRoot;
            }
        }
        pNode _pRoot;
        Heap<W> hp;
    };
    int main()
    {
        int array[] = { 5, 3, 2, 7 };
        HuffmanTree<int>h(array, 4, 0);
        system("pause");
        return 0;
    }

    struct compare
    {
    bool operator()(pNode pLeft, pNode Pright)
    {
    return pLeft->_weight < Pright->_weight;
    }
    };
    关于此结构的说明:
    我们需要将节点保存在堆中,但是在结构体中是节点的地址,则需要比较其权值,之后进行调整。

    展开全文
  • ——哈夫曼

    2018-07-24 16:19:42
    哈夫曼的构造:  从给定的n个数中,选两次最小值,将这两个数的和...利用堆构建哈夫曼: #include&lt;stdio.h&gt; #include&lt;string.h&gt; #include&lt;stdlib.h&gt; #define M...
  • Java代码构造哈夫曼

    2021-03-12 23:55:18
    2、构造哈弗曼编码 哈夫曼提出构造最优前缀码的贪心算法,由此产生的编码方案称为哈夫曼编码。其构造步骤如下: (1)哈夫曼算法以自底向上的方式构造表示最优前缀码的二叉树T。 (2)算法以|C|个叶结点开始,执行|C|-...
  • 不懂的自行查阅哈弗曼树构建过程 题目 哈弗曼树,第一行录入一个数n,表示叶节点的个数,需要用这些叶节点生成哈弗曼树,根据哈弗曼树的概念,这些节点有权值,即weight,题目需要输入所有节点的值与权值的乘积...
  • 哈夫曼原理,及构造方法

    万次阅读 多人点赞 2018-08-05 12:13:21
    哈夫曼(最优二叉树) 百度百科:https://baike.baidu.com/item/%E5%93%88%E5%A4%AB%E6%9B%BC%E6%A0%91/2305769?fr=aladdin 一. 目的: 找出存放一串字符所需的最少的二进制编码 二. 构造方法: 首先统计出每...
  • 哈弗曼树的创建 带权路径长度的计算 #include&lt;iostream&gt; #include&lt;cstdio&gt; #include&lt;cstring&gt; #include&lt;cstdlib&gt; #include &lt;iomanip&gt; ...
  • 哈夫曼的构造(C语言实现)

    万次阅读 多人点赞 2018-12-06 17:48:27
    哈夫曼的构造过程可以详见推荐博客:哈夫曼以及哈夫曼编码的构造步骤 建议先看完推荐博客中的文字说明,或者自己找一本数据结构的来仔细阅读以下关于哈夫曼的构造 然后再来看下面给出的code 这里给出的是...
  • 数据结构与算法之构建哈夫曼

    千次阅读 2020-03-07 11:25:13
    哈夫曼的介绍 Huffman Tree,中文名是哈夫曼或霍夫曼或者赫夫曼,它是最优二叉树。 定义:给定n个权值作为n个叶子结点,构造一棵二叉树,若的带权路径长度达到最小,则这棵被称为哈夫曼。 (01) 路径和...
  • 哈夫曼

    2021-04-27 16:49:31
    哈夫曼的概念 结点的权:具有一定权重的数值 结点的带权路径长度:从的根到该结点的路径长度(经过的边数)与该结点上权值的乘积 的带权路径长度:中所有叶结点的带权路径长度之和(WPL, Weight Path Length),...
  • 数据结构--哈夫曼

    千次阅读 2022-03-03 21:32:43
    哈夫曼及其应用 1、哈夫曼的基本概念 路径:从中一个结点到另一个结点之间的分支构成这两个结点间的路径 结点的路径长度:两结点间路径上的分支数。 的路径长度:从树根到每一个结点的路径...
  • 哈夫曼又称作最优二叉树,是带权路径长度最小的二叉树。 一、算法步骤: 构造哈夫曼算法的实现可以分成两大部分。 ①初始化:首先动态申请2n个单元;然后循环2n-1次,从1号单元开始,依次将1至m所有单元中的...
  • 其实基本是基于C的代码实现的,时间复杂度还可以,变量比较多,但思路很清晰。
  • 构造哈夫曼C++实现

    千次阅读 2020-07-02 16:46:04
    给定N个权值作为N个叶子结点,构造一棵二叉树,若该的带权路径长度达到最小,称这样的二叉树为最优二叉树,也称为哈夫曼(Huffman Tree)。 哈夫曼是带权路径长度最短的,权值较大的结点离根较近。 步骤 求{11...
  • 哈夫曼构建、编码以及带权路径长计算

    万次阅读 多人点赞 2018-09-17 14:17:58
    给定n个权值作为n个叶子结点,构造一棵二叉树,若该的带权路径长度达到最小,称这样的二叉树为最优二叉树,也称为哈夫曼(Huffman Tree)。哈夫曼是带权路径长度最短的,权值较大的结点离根较近。 构造哈夫曼...
  • 理解哈夫曼树构建哈夫曼表 一、哈夫曼的作用 哈夫曼是一个二叉树,是可以将一些字节重新编码 ,而且能够使用最少的空间。所以也叫最优二叉树。 比如这段字符串 ...
  • 一、哈夫曼的概念 哈夫曼也叫最优二叉树,在了解他的定义之前,我们先来看看以下这几个词的定义。 1、背景定义 ????路径:从中一个节点到另一个节点间的分支构成这两个节点间的路径。 ????路径长度:路径...
  • 哈夫曼之C#实现

    2020-04-22 20:05:37
    关于哈夫曼的讲解请参考上篇《三步学通哈夫曼》(https://blog.csdn.net/helloworldchina/article/details/105210054),这里笔者仅补充一下C#代码的实现。见下: 1 c#代码 using System; using System....
  • 哈夫曼的构造算法代码

    千次阅读 2020-05-05 21:24:19
    代码: #include<stdio.h> #define ERROR 0 #define OK 1 typedef int Status; //采用顺序存储结构,一维结构数组 //定义结点类型 typedef struct { int weight; int parent,lch,rch;...//哈夫曼...
  • c语言哈夫曼构造代码

    千次阅读 2021-04-03 22:43:38
    c语言哈夫曼构造代码 博主就很掘的一个人,最近学哈夫曼,想着用指针去实现,觉得用指针实现,内存消耗会更少,写到后面发现越来与麻烦,且内存开销并没有减少,于是还是使用结构体数组中规中矩的去实现哈夫曼...
  • c语言构造哈夫曼-哈夫曼编码

    万次阅读 多人点赞 2018-12-05 14:59:59
    构造哈夫曼 首先,我们需要了解哈夫曼是什么: 一.相关知识点 路径: 路径是指从一个节点到另一个节点的分支序列。 路径长度: 指从一个节点到另一个结点所经过的分支数目。 ,从根节点到a的分支数目是2, 数...
  • 数据结构8--哈夫曼

    千次阅读 2021-08-09 19:55:17
    哈夫曼与哈夫曼编码哈夫曼 哈夫曼
  • 什么是哈夫曼 在介绍哈夫曼前,我们先介绍二叉树的基本概念,以便大家更好地理解哈夫曼: 路径:两个节点之间分支的连线即两个节点之间的路径。 路径长:两个节点之间路径所包含分支的和。 深度:根节点...
  • 数据结构之哈夫曼

    千次阅读 2020-12-18 19:46:34
    一、什么是哈夫曼 基本介绍 1.给定n个权值作为n个叶子结点,构造一棵二叉树,若该的带权路径长度1(wpl)达到最小,称这样的二叉树为最优叉。也称为哈夫曼(HuffmanTree),还有的书翻译为霍夫曼。 wpl:...
  • 哈夫曼又称最优二叉树 给定N个权值作为N个叶子结点,构造一棵二叉树,若该的带权路径长度达到最小,称这样的二叉树为最优二叉树,也称为哈夫曼(Huffman Tree)。哈夫曼是带权路径长度最短的,权值较大的...

空空如也

空空如也

1 2 3 4 5 ... 10
收藏数 186
精华内容 74
关键字:

构建哈弗曼树csdn

友情链接: LiteNAdemo_https.zip