一、堆(Heap)數(shù)據(jù)結(jié)構(gòu)的用處

1、高效定時(shí)器

假設(shè)我們要設(shè)計(jì)一個(gè)定時(shí)器，定時(shí)器中維護(hù)了很多定時(shí)任務(wù)，每個(gè)任務(wù)都設(shè)定了一個(gè)要觸發(fā)執(zhí)行的時(shí)間點(diǎn)。定時(shí)器每過(guò)一個(gè)很小的單位時(shí)間（比如 1 秒），就掃描一遍任務(wù)，看是否有任務(wù)到達(dá)設(shè)定的執(zhí)行時(shí)間。如果到達(dá)了，就拿出來(lái)執(zhí)行。

像這樣每次掃描的時(shí)候，把所有任務(wù)都掃描一遍，肯定很低效，如果任務(wù)比較少還好，任務(wù)比較多的話，就比較耗時(shí)。那有更高效的辦法呢？答案是有的。

我們可以把每個(gè)任務(wù)都存儲(chǔ)在優(yōu)先級(jí)隊(duì)列中(以觸發(fā)時(shí)間為優(yōu)先級(jí)的小頂堆)，這樣最先執(zhí)行的任務(wù)就在堆頂。每次掃描的時(shí)候只需取出堆頂任務(wù)，拿對(duì)于任務(wù)的定時(shí)時(shí)間和當(dāng)前時(shí)間比較。

假設(shè)任務(wù)執(zhí)行時(shí)間與當(dāng)前時(shí)間的差為T(mén)。如果T<=0，就從隊(duì)列中刪除任務(wù)，并執(zhí)行。否則定時(shí)器就可以設(shè)定在T秒之后再執(zhí)行任務(wù)。從當(dāng)前時(shí)間到T-1秒的時(shí)間內(nèi)定時(shí)器不需要做任何事情。

Ps:假如我們需要為一個(gè)任務(wù)設(shè)定循環(huán)定時(shí)器，可以在取出堆頂任務(wù)后，將下一次任務(wù)的觸發(fā)執(zhí)行的時(shí)間重新加入到優(yōu)先級(jí)隊(duì)列。感興趣的同學(xué)可以將上述堆的代碼改造一下，將num位置的參數(shù)改造為一個(gè)對(duì)象。調(diào)整堆的時(shí)候按照對(duì)象的key作為優(yōu)先級(jí)調(diào)整堆。

2、合并小文件

假設(shè)我們有 100 個(gè)小文件，每個(gè)文件的大小是 100MB，每個(gè)文件中存儲(chǔ)的都是有序的字符串。我們希望將這些 100 個(gè)小文件合并成一個(gè)有序的大文件。

思路：名列前茅趟從這100個(gè)小文件中各取出名列前茅個(gè)字符串并加入到小頂堆中，此時(shí)堆頂元素是最小的。取出堆頂元素存入合并后的大文件。假如這個(gè)最小字符串在10.txt這個(gè)小文件中，我們就再?gòu)倪@個(gè)小文件取下一個(gè)字符串，加入到堆中，重新從堆中取出堆頂元素并放入合并后的大文件。依此類推，直到所有文件中的數(shù)據(jù)都放入到大文件為止。

3、較好熱門(mén)關(guān)鍵詞

有一個(gè)包含 10 億個(gè)搜索關(guān)鍵詞的日志文件，如何快速獲取到 前二0 最熱門(mén)的搜索關(guān)鍵詞呢？

Ps:假設(shè)10億條數(shù)據(jù)不重復(fù)的有1億條，每個(gè)關(guān)鍵詞占有50個(gè)字節(jié)，不重復(fù)關(guān)鍵詞的總大小約為4.6G。如果計(jì)算機(jī)內(nèi)存限定為1G，如何處理呢？

思路：將10億個(gè)關(guān)鍵詞按hash算法放到到10個(gè)文件中，重復(fù)的關(guān)鍵字會(huì)被放到同一個(gè)文件中。分別計(jì)算每個(gè)文件的前二0,然后把10個(gè)前二0 放在一起，然后取出100個(gè)關(guān)鍵詞中，出現(xiàn)次數(shù)非常多的10個(gè)關(guān)鍵詞，就是最終求得多前二0。

到這里堆的相關(guān)應(yīng)用內(nèi)容就介紹完了，堆是一種很好的數(shù)據(jù)結(jié)構(gòu)，能解決很多實(shí)用問(wèn)題，希望作者的博文能幫助您更好的學(xué)習(xí)理解堆。本文中的代碼都是作者親自實(shí)踐的，可以直接拷貝下來(lái)學(xué)習(xí)參考。

延伸閱讀：

二、堆是什么

堆是一種完全二叉樹(shù)，復(fù)習(xí)一下完全二叉樹(shù)的定義，完全二叉樹(shù)的形式是指除了最后一層之外，其他所有層的結(jié)點(diǎn)都是滿的，而最后一層的所有結(jié)點(diǎn)都靠左邊。若設(shè)二叉樹(shù)的深度為h，除第 h 層外，其它各層 (1～h-1) 的結(jié)點(diǎn)數(shù)都達(dá)到最大個(gè)數(shù)，第 h 層所有的結(jié)點(diǎn)都連續(xù)集中在最左邊，這就是完全二叉樹(shù)。而最小堆要求，對(duì)于任意一個(gè)父結(jié)點(diǎn)來(lái)說(shuō)，其子結(jié)點(diǎn)的值都大于這個(gè)父節(jié)點(diǎn),同理，最大堆就是說(shuō)，其子節(jié)點(diǎn)的值都小于這個(gè)父節(jié)點(diǎn)。