(3)其他應(yīng)用

　　可使用堆解決下列問(wèn)題：

　　<>1.構(gòu)建哈夫曼代碼：

　　我們知道在構(gòu)建哈夫曼樹(shù)時(shí)，每次要選擇集合中兩個(gè)最小的元素，然后將元素值相加，合并為一個(gè)新節(jié)點(diǎn)，此時(shí)兩個(gè)最小的元素的取出可以用HeapExtractMin函數(shù)來(lái)實(shí)現(xiàn)，產(chǎn)出的新節(jié)點(diǎn)需要插入到堆中，我們有MinHeapInsert函數(shù)來(lái)實(shí)現(xiàn)。

　　<>2.計(jì)算大型浮點(diǎn)數(shù)集合的和：

　　我們知道大浮點(diǎn)數(shù)和小浮點(diǎn)數(shù)相加，很可能會(huì)造成精度誤差。所以可以每次從優(yōu)先級(jí)隊(duì)列中取出最小的兩個(gè)數(shù)相加，和1的實(shí)現(xiàn)差不多。

　　<>3.將多個(gè)小型有序文件合并到一個(gè)大型有序文件中：

　　假設(shè)有 n個(gè)小型有序文件，建立一個(gè)大小為n的最小堆，每個(gè)有序文件貢獻(xiàn)一個(gè)(如果有的話(huà))，每次取出最小值插入到大型文件中，并且去掉該最小元素，并將它在文件中的后續(xù)元素插入到堆中,能夠在o(lgn)的時(shí)間內(nèi)從n個(gè)文件中選擇要插入到大型文件中的元素。

　　<>4.在具有10億個(gè)數(shù)值的集合中找到100萬(wàn)個(gè)最大的數(shù)：

　　建立100萬(wàn)個(gè)元素的最小二叉堆，后面的數(shù)和根部進(jìn)行比較，如果大于根部，進(jìn)行堆調(diào)整。

　　1.n×m遍掃描

　　【算法基本描述】n×m遍掃描

　　【算法復(fù)雜度】O(nm)

　　【算法思想】每次都掃描一遍數(shù)組，取出最大元素，這樣掃描m遍就能得到m個(gè)最大的數(shù)。

　　2.排序后取最大m個(gè)數(shù)

　　【算法基本描述】對(duì)n個(gè)數(shù)排序，對(duì)拍完序后的序列取m個(gè)最大的數(shù)

　　【算法復(fù)雜度】視排序的復(fù)雜度，一般為O(nlogn)或O(n^2)

　　3.最小堆

　　【算法基本描述】一遍掃描+最小堆

　　【算法復(fù)雜度】O(nlogm) 遍歷O(n) 最小堆O(logm)

　　【算法偽代碼】

　　建立一個(gè)最小堆(優(yōu)先隊(duì)列)，最小堆的大小控制在m之內(nèi);

　　for 每個(gè)數(shù)：

　　if 這個(gè)數(shù)比最小堆的堆頂元素大：

　　彈出最小堆的最小元素，

　　*把這個(gè)數(shù)插入到最小堆;

　　最小堆中的m個(gè)元素就是所要求的元素;

　　中最小堆的作用就是保持里面始終有m個(gè)最大元素，且m個(gè)元素中最小的元素在堆頂。

　　【其他】如果要求n個(gè)數(shù)中取最小的m個(gè)，只要大頂堆即可

　　總結(jié)：當(dāng)n與m差不多大時(shí)，采用復(fù)雜度較低的排序是比較可取的，因?yàn)楹?jiǎn)單。當(dāng)m<

　　我不敢說(shuō)我的算法是最好的，但是它一定是一個(gè)復(fù)雜度較低的算法。

　　使用用最小堆來(lái)找最大的K個(gè)數(shù)源碼：

　　軟考程序員考試歷年真題重點(diǎn)題總結(jié)及答案

　　2011年上半年軟考報(bào)名時(shí)間及方式匯總

　　軟考程序員考試歷年真題匯總(2007年-2010年)