第四十章貪心算法——Huffman樹-創(chuàng)新互聯(lián)
- 一、問題
- 二、思路
- 1、哈夫曼樹算法
- 2、算法實現(xiàn)
- 三、代碼
這道題是一道經典的哈夫曼問題，解決的方案就是我們每次挑出兩堆最小的果子合并。那么這個合并的過程可以畫成一棵完全二叉樹。如下圖所示：
那么怎計算呢？其實就是把除了根節(jié)點以為的點所富有的權值加在一起即可。
如下圖所示：
我們對上述的計算式子稍作變形，就會發(fā)現(xiàn)圖中紅色式子的規(guī)律。
那么為什么這個算法就能保證最小呢？
其實感性的理解一下也是可以知道的，越靠下的節(jié)點，被算的次數(shù)是越多的，因此我們讓這些算的次數(shù)多的節(jié)點帶有一個較小的權值，這樣就能保證整體最小。
嚴格的證明方法的話，大家可以采用反證法。這里就不多介紹了。
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)定的海外服務器提供商？創(chuàng)新互聯(lián)www.cdcxhl.cn海外機房具備T級流量清洗系統(tǒng)配攻擊溯源，準確流量調度確保服務器高可用性，企業(yè)級服務器適合批量采購，新人活動首月15元起，快前往官網查看詳情吧
分享標題：第四十章貪心算法——Huffman樹-創(chuàng)新互聯(lián)
轉載注明：http://aaarwkj.com/article10/dshpdo.html
成都網站建設公司_創(chuàng)新互聯(lián)，為您提供做網站、網站維護、網站營銷、面包屑導航、建站公司、自適應網站
聲明：本網站發(fā)布的內容（圖片、視頻和文字）以用戶投稿、用戶轉載內容為主，如果涉及侵權請盡快告知，我們將會在第一時間刪除。文章觀點不代表本網站立場，如需處理請聯(lián)系客服。電話：028-86922220；郵箱：631063699@qq.com。內容未經允許不得轉載，或轉載時需注明來源： 創(chuàng)新互聯(lián)
猜你還喜歡下面的內容
- 虛擬主機和云服務器到底有什么不同之處？ 2016-11-05
- 再談虛擬主機和域名的選購技巧 2021-06-27
- 阿里云虛擬主機PHP session不可用，網站后臺無法登錄 2023-06-25
- 虛擬主機有什么用 2021-02-18
- 帶您了解如何購買國外虛擬主機 2016-11-02
- 如何選擇適合自己的云主機？云主機和虛擬主機有何不同？ 2022-10-02
- 虛擬主機如何設置404頁面? 2014-10-22
- 云服務器和虛擬主機的區(qū)別主要有哪些？ 2022-10-06
- 在SEO的角度我們怎么選擇虛擬主機更好 2021-04-13
- 如何選購虛擬主機？ 2022-07-31
- 上海網站建設之如何選擇虛擬主機 2022-09-24
- 云虛擬主機和云服務器究竟怎么選擇比較好？ 2022-10-12