第四十章貪心算法——Huffman樹-創(chuàng)新互聯(lián)

貪心算法——Huffman樹
  • 一、問題
  • 二、思路
    • 1、哈夫曼樹算法
    • 2、算法實現(xiàn)
  • 三、代碼

成都創(chuàng)新互聯(lián)公司專業(yè)為企業(yè)提供炎陵網(wǎng)站建設(shè)、炎陵做網(wǎng)站、炎陵網(wǎng)站設(shè)計、炎陵網(wǎng)站制作等企業(yè)網(wǎng)站建設(shè)、網(wǎng)頁設(shè)計與制作、炎陵企業(yè)網(wǎng)站模板建站服務(wù)，十多年炎陵做網(wǎng)站經(jīng)驗，不只是建網(wǎng)站，更提供有價值的思路和整體網(wǎng)絡(luò)服務(wù)。一、問題

在這里插入圖片描述

二、思路 1、哈夫曼樹算法

這道題是一道經(jīng)典的哈夫曼問題，解決的方案就是我們每次挑出兩堆最小的果子合并。那么這個合并的過程可以畫成一棵完全二叉樹。如下圖所示：
在這里插入圖片描述
那么怎計算呢？其實就是把除了根節(jié)點以為的點所富有的權(quán)值加在一起即可。
如下圖所示：
在這里插入圖片描述
我們對上述的計算式子稍作變形，就會發(fā)現(xiàn)圖中紅色式子的規(guī)律。

那么為什么這個算法就能保證最小呢？

其實感性的理解一下也是可以知道的，越靠下的節(jié)點，被算的次數(shù)是越多的，因此我們讓這些算的次數(shù)多的節(jié)點帶有一個較小的權(quán)值，這樣就能保證整體最小。

嚴(yán)格的證明方法的話，大家可以采用反證法。這里就不多介紹了。

2、算法實現(xiàn)

我們每次都是選出兩個最小的，對于這種從一堆數(shù)字中選出前幾個最小的值，這種情形下，我們可以采用小根堆。

三、代碼
#include#includeusing namespace std;
int main()
{priority_queue,greater>q;
    int n,ans=0;
    cin>>n;
    for(int i=0;iint x;
        scanf("%d",&x);
        q.push(x);
    }
    while(q.size()>1)
    {int top1=q.top();
        q.pop();
        int top2=q.top();
        q.pop();
        ans+=top1+top2;
        q.push(top1+top2);
    }
    cout<

你是否還在尋找穩(wěn)定的海外服務(wù)器提供商？創(chuàng)新互聯(lián)www.cdcxhl.cn海外機房具備T級流量清洗系統(tǒng)配攻擊溯源，準(zhǔn)確流量調(diào)度確保服務(wù)器高可用性，企業(yè)級服務(wù)器適合批量采購，新人活動首月15元起，快前往官網(wǎng)查看詳情吧

分享標(biāo)題：第四十章貪心算法——Huffman樹-創(chuàng)新互聯(lián)
轉(zhuǎn)載注明：http://muchs.cn/article10/dshpdo.html

成都網(wǎng)站建設(shè)公司_創(chuàng)新互聯(lián)，為您提供做網(wǎng)站、網(wǎng)站維護、網(wǎng)站營銷、面包屑導(dǎo)航、建站公司、自適應(yīng)網(wǎng)站

廣告

聲明：本網(wǎng)站發(fā)布的內(nèi)容（圖片、視頻和文字）以用戶投稿、用戶轉(zhuǎn)載內(nèi)容為主，如果涉及侵權(quán)請盡快告知，我們將會在第一時間刪除。文章觀點不代表本網(wǎng)站立場，如需處理請聯(lián)系客服。電話：028-86922220；郵箱：631063699@qq.com。內(nèi)容未經(jīng)允許不得轉(zhuǎn)載，或轉(zhuǎn)載時需注明來源： 創(chuàng)新互聯(lián)