資料結構與算法-學習筆記（21）

堆的應用

優先級隊列

按優先級來，優先級最高的，最先出隊。可以用堆來實作。

1. 合并有序小檔案 假設有100個大小為100MB小檔案，每個檔案中存儲的都是有序的字元串。如何将這100個小檔案合并成一個有序大檔案。

思路：同樣采用合并兩個有序數組的方式。從100個檔案中各取第一個字元串，放入一個數組中比較大小，把最小的字元串放入合并後的大檔案中，并從比較大小的數組中删除。然後在從最小字元串的來源檔案再取一個字元串放入數組中比較大小，依次進行直到一個檔案字元取完，就隻比較剩餘的檔案。

主要問題就是取100個元素中最小的元素，可以使用小頂堆排序，每次删除堆頂元素和插入新元素。這樣更為高效。

1. 高效能定時器

在一個定時器中會維護很多定時認為，每個人物都設定一個觸發執行時間，定時器每隔1s掃描一遍任務清單，檢視此時應該觸發哪個任務執行。

但是這種方式明顯很低效：1. 目前并沒有要觸發的任務；2. 任務清單很大，掃描耗時。

是以我們可以把最近的時間點（時間最小值）任務拿出來，每次隻掃描最近的任務，檢視此時與任務觸發時間的內插補點T，再間隔時間T後再執行任務，同時删除該任務，查找剩餘最小值。

這個過程也就聯想到了小頂堆，把任務按照觸發時間排成小頂堆，每次掃描執行堆頂，删除堆頂。

利用堆求Top K

該問題有兩類：一類針對靜态資料集合（資料不變）。一類針對動态資料集合（資料是變動的）。

1. 靜态資料集合 在n資料的數組中，查找前K大資料？

維護一個大小為K的小頂堆（最終讓它存儲最大的K個元素），是以每次從數組中取一個元素和小頂堆堆頂比較：< 不處理，繼續周遊數組；>插入小頂堆中。等數組周遊完成，也就找到了前K大資料。

最壞的時間複雜度O(nlogK)。

利用堆求中位數

中位數：處在中間位置的資料。 如果資料是靜态的，那麼求中位數其實就是求第n/2小的資料，也就是求index=n/2的元素，那麼用快速排序的思想就可以做了。

如果資料是動态的，不能每次資料變化就排序一次太低效，是以可以使用堆。

以此類推，兩個堆不僅可以就覺求中位數的問題，還可以快速求出其他百分位的資料，原理類似。

習題

在一個包含10億個搜尋關鍵字的日志檔案中如何快速擷取到Top10最熱（搜尋次數最多）關鍵詞。

TopN想到使用前面的堆排序來做，但是10億個關鍵詞，肯定沒法一下子都加在到記憶體中，是以我們聯想到之前哈希函數時的應用分布式。那如果我不講資料分到不同的計算機中，僅僅把10億資料分片到10個檔案中也是一樣的。同樣使用哈希函數求餘數的方式将10億資料分到10個檔案中。再在這個檔案中利用字典（或者其他散清單key（關鍵字）-value（出現次數））。之後再使用大小為10的最小堆，分别對10個檔案逐個比較計算，直到全部比較完。

如果資料是實時更新的怎麼辦？

按照分片的規則把新資料插入到合适的字典中，再拿這個資料的value去和堆頂比較。

轉載于:https://juejin.im/post/5c0de1d46fb9a04a0955df2f