一、堆(Heap)數(shù)據(jù)結(jié)構(gòu)的用處
1、高效定時器
假設(shè)我們要設(shè)計一個定時器,定時器中維護了很多定時任務(wù),每個任務(wù)都設(shè)定了一個要觸發(fā)執(zhí)行的時間點。定時器每過一個很小的單位時間(比如 1 秒),就掃描一遍任務(wù),看是否有任務(wù)到達設(shè)定的執(zhí)行時間。如果到達了,就拿出來執(zhí)行。
像這樣每次掃描的時候,把所有任務(wù)都掃描一遍,肯定很低效,如果任務(wù)比較少還好,任務(wù)比較多的話,就比較耗時。那有更高效的辦法呢?答案是有的。
我們可以把每個任務(wù)都存儲在優(yōu)先級隊列中(以觸發(fā)時間為優(yōu)先級的小頂堆),這樣最先執(zhí)行的任務(wù)就在堆頂。每次掃描的時候只需取出堆頂任務(wù),拿對于任務(wù)的定時時間和當前時間比較。
假設(shè)任務(wù)執(zhí)行時間與當前時間的差為T。如果T<=0,就從隊列中刪除任務(wù),并執(zhí)行。否則定時器就可以設(shè)定在T秒之后再執(zhí)行任務(wù)。從當前時間到T-1秒的時間內(nèi)定時器不需要做任何事情。
Ps:假如我們需要為一個任務(wù)設(shè)定循環(huán)定時器,可以在取出堆頂任務(wù)后,將下一次任務(wù)的觸發(fā)執(zhí)行的時間重新加入到優(yōu)先級隊列。感興趣的同學(xué)可以將上述堆的代碼改造一下,將num位置的參數(shù)改造為一個對象。調(diào)整堆的時候按照對象的key作為優(yōu)先級調(diào)整堆。
2、合并小文件
假設(shè)我們有 100 個小文件,每個文件的大小是 100MB,每個文件中存儲的都是有序的字符串。我們希望將這些 100 個小文件合并成一個有序的大文件。
思路:名列前茅趟從這100個小文件中各取出名列前茅個字符串并加入到小頂堆中,此時堆頂元素是最小的。取出堆頂元素存入合并后的大文件。假如這個最小字符串在10.txt這個小文件中,我們就再從這個小文件取下一個字符串,加入到堆中,重新從堆中取出堆頂元素并放入合并后的大文件。依此類推,直到所有文件中的數(shù)據(jù)都放入到大文件為止。
3、較好熱門關(guān)鍵詞
有一個包含 10 億個搜索關(guān)鍵詞的日志文件,如何快速獲取到 前二0 最熱門的搜索關(guān)鍵詞呢?
Ps:假設(shè)10億條數(shù)據(jù)不重復(fù)的有1億條,每個關(guān)鍵詞占有50個字節(jié),不重復(fù)關(guān)鍵詞的總大小約為4.6G。如果計算機內(nèi)存限定為1G,如何處理呢?
思路:將10億個關(guān)鍵詞按hash算法放到到10個文件中,重復(fù)的關(guān)鍵字會被放到同一個文件中。分別計算每個文件的前二0,然后把10個前二0 放在一起,然后取出100個關(guān)鍵詞中,出現(xiàn)次數(shù)非常多的10個關(guān)鍵詞,就是最終求得多前二0。
到這里堆的相關(guān)應(yīng)用內(nèi)容就介紹完了,堆是一種很好的數(shù)據(jù)結(jié)構(gòu),能解決很多實用問題,希望作者的博文能幫助您更好的學(xué)習(xí)理解堆。本文中的代碼都是作者親自實踐的,可以直接拷貝下來學(xué)習(xí)參考。
延伸閱讀:
二、堆是什么
堆是一種完全二叉樹,復(fù)習(xí)一下完全二叉樹的定義,完全二叉樹的形式是指除了最后一層之外,其他所有層的結(jié)點都是滿的,而最后一層的所有結(jié)點都靠左邊。若設(shè)二叉樹的深度為h,除第 h 層外,其它各層 (1~h-1) 的結(jié)點數(shù)都達到最大個數(shù),第 h 層所有的結(jié)點都連續(xù)集中在最左邊,這就是完全二叉樹。而最小堆要求,對于任意一個父結(jié)點來說,其子結(jié)點的值都大于這個父節(jié)點,同理,最大堆就是說,其子節(jié)點的值都小于這個父節(jié)點。