堆的應用一：優(yōu)先級隊列
優(yōu)先級隊列，顧名思義逝段，它首先應該是一個隊列垛玻。
隊列最大的特性就是先進先出。不過奶躯，在優(yōu)先級隊列中帚桩，數(shù)據(jù)的出隊順序不是先進先出，而是按照優(yōu)先級來嘹黔，優(yōu)先級最高的账嚎，最先出隊。
一個堆就可以看作一個優(yōu)先級隊列儡蔓。很多時候郭蕉，它們只是概念上的區(qū)分而已。往優(yōu)先級隊列中插入一個元素喂江，就相當于往堆中插入一個元素召锈；從優(yōu)先級隊列中取出優(yōu)先級最高的元素，就相當于取出堆頂元素开呐。
1. 合并有序小文件
假設我們有100個小文件烟勋，每個文件的大小是100MB，每個文件中存儲的都是有序的字符串筐付。我們希望將這些 100 個小文件合并成一個有序的大文件卵惦。
我們將從小文件中取出來的字符串放入到小頂堆中，那堆頂?shù)脑赝咂荩簿褪莾?yōu)先級隊列隊首的元素沮尿，就是最小的字符串。我們將這個字符串放入到大文件中，并將其從堆中刪除畜疾。然后再從小文件中取出下一個字符串赴邻，放入到堆中。循環(huán)這個過程啡捶，就可以將100個小文件中的數(shù)據(jù)依次放入到大文件中姥敛。
2. 高性能定時器
堆的應用二：利用堆求 Top K
這種求 Top K 的問題抽象成兩類。一類是針對靜態(tài)數(shù)據(jù)集合瞎暑，也就是說數(shù)據(jù)集合事先確定彤敛，不會再變。另一類是針對動態(tài)數(shù)據(jù)集合了赌，也就是說數(shù)據(jù)集合事先并不確定墨榄，有數(shù)據(jù)動態(tài)地加入到集合中。
靜態(tài)數(shù)據(jù)集合
維護一個大小為K的小頂堆勿她，順序遍歷數(shù)組袄秩，從數(shù)組中取出數(shù)據(jù)與堆頂元素比較。如果比堆頂元素大逢并，我們就把堆頂元素刪除之剧，并且將這個元素插入到堆中；如果比堆頂元素小筒狠，則不做處理猪狈，繼續(xù)遍歷數(shù)組。這樣等數(shù)組中的數(shù)據(jù)都遍歷完之后辩恼，堆中的數(shù)據(jù)就是前 K 大數(shù)據(jù)了雇庙。
遍歷數(shù)組需要O(n)的時間復雜度，一次堆化操作需要O(logK)的時間復雜度灶伊，所以最壞情況下疆前，n 個元素都入堆一次，時間復雜度就是 O(nlogK)聘萨。
動態(tài)數(shù)據(jù)集合
維護一個 K 大小的小頂堆竹椒，當有數(shù)據(jù)被添加到集合中時，我們就拿它與堆頂?shù)脑貙Ρ让追Ｈ绻榷秧斣卮笮赝辏覀兙桶讯秧斣貏h除，并且將這個元素插入到堆中翘贮；如果比堆頂元素小赊窥，則不做處理。這樣狸页，無論任何時候需要查詢當前的前 K 大數(shù)據(jù)锨能，我們都可以立刻返回給他。
堆的應用三：利用堆求中位數(shù)
靜態(tài)數(shù)據(jù)
對于一組靜態(tài)數(shù)據(jù)，中位數(shù)是固定的熄阻，我們可以先排序，第n/2個數(shù)據(jù)就是中位數(shù)倔约。每次詢問中位數(shù)的時候秃殉，我們直接返回這個固定的值就好了。所以跺株，盡管排序的代價比較大，但是邊際成本會很小。
動態(tài)數(shù)據(jù)
我們需要維護兩個堆畦木，一個大頂堆十籍，一個小頂堆蛆封。大頂堆中存儲前半部分數(shù)據(jù)惨篱，小頂堆中存儲后半部分數(shù)據(jù)围俘，且小頂堆中的數(shù)據(jù)都大于大頂堆中的數(shù)據(jù)簿寂。
