貪心算法——Huffman樹

• 一、問題
• 二、思路
• • 1、哈夫曼樹算法
  • 2、算法實現
• 三、代碼

成都創新互聯公司專業為企業提供炎陵網站建設、炎陵做網站、炎陵網站設計、炎陵網站制作等企業網站建設、網頁設計與制作、炎陵企業網站模板建站服務，十多年炎陵做網站經驗，不只是建網站，更提供有價值的思路和整體網絡服務。一、問題

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

這道題是一道經典的哈夫曼問題，解決的方案就是我們每次挑出兩堆最小的果子合并。那么這個合并的過程可以畫成一棵完全二叉樹。如下圖所示：

那么怎計算呢？其實就是把除了根節點以為的點所富有的權值加在一起即可。
如下圖所示：

我們對上述的計算式子稍作變形，就會發現圖中紅色式子的規律。

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

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

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

2、算法實現

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

三、代碼

#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<

你是否還在尋找穩定的海外服務器提供商？創新互聯www.cdcxhl.cn海外機房具備T級流量清洗系統配攻擊溯源，準確流量調度確保服務器高可用性，企業級服務器適合批量采購，新人活動首月15元起，快前往官網查看詳情吧

當前題目：第四十章貪心算法——Huffman樹-創新互聯
URL鏈接：http://m.jcarcd.cn/article/dshpdo.html