上一節(jié)我們學習了堆和堆排序的一些理論知識（點擊查看）役纹，今天我們就來講一講焰望，堆這種數(shù)據(jù)結(jié)構(gòu)的幾個非常重要的應用稽鞭。
應用一：優(yōu)先級隊列
優(yōu)先隊隊列避除，是一個按優(yōu)先級進出的特殊隊列，一般的隊列是先進先出翘盖，而優(yōu)先級隊列是優(yōu)先級高的先出滤否。
優(yōu)先級隊列與堆非常相似，一個堆可以看作一個優(yōu)先級隊列最仑。往優(yōu)先隊隊列插入一個元素，相當于往堆中插入一個元素炊甲；從優(yōu)先級隊列中取出優(yōu)先級最高的元素泥彤，就相當于取出堆頂元素。
例子1：合并有序小文件
合并多個有序的小文件到大文件卿啡。假設有100個文件吟吝，要合并到1個文件里，要求有序颈娜。
定義一個大小為100的小頂堆剑逃，從100個文件里取出第一行，初始化小頂堆官辽。然后取出堆頂放進大文件里蛹磺，并從此數(shù)據(jù)所在的文件里再取出一行放到堆里（重新堆化），重復這個動作同仆，直到所有文件的內(nèi)容都為空萤捆。
例子2：高性能定時器
定時器維護多個定時任務，每個任務都設置了觸發(fā)執(zhí)行的時間點。
計算每個任務的時間差俗或，弄成小頂堆市怎。取堆頂元素的時間差，讓程序睡眠辛慰，睡眠時間為此時間差区匠，程序喚醒后，取出堆頂任務（刪除堆頂元素）并執(zhí)行帅腌。如果任務是重復的驰弄，再重新計算任務的時間差，并插入堆里狞膘。
應用二：利用堆求Top K
抽象成兩類問題：靜態(tài)數(shù)據(jù)集合和動態(tài)數(shù)據(jù)集合
實現(xiàn)方式：定義一個大小為K的小頂堆揩懒，順序遍歷數(shù)組，逐一與堆頂進行比較挽封，假設比它大已球，則刪除堆頂再插入后堆化。假設小于等于它辅愿，則忽略智亮。
對于動態(tài)數(shù)組，可維護一個實時的堆点待，當有數(shù)據(jù)插入數(shù)組阔蛉，與堆頂判斷，比它大則插入堆癞埠，否則忽略状原。并且插入到數(shù)組中。
時間復雜度：O(nlogk)苗踪。遍歷數(shù)組O(n)颠区，每次替換（堆化）O(logk)。
應用三：利用堆求中位數(shù)
中位數(shù)指在有序數(shù)據(jù)中處于中間位置的那個數(shù)據(jù)通铲。如果數(shù)據(jù)個數(shù)為奇數(shù)毕莱，則中位數(shù)是n/2+1位置的數(shù)，如果是偶數(shù)颅夺，則是n/2和n/2+1朋截，可取其中的任意一個。
分兩種情況：靜態(tài)數(shù)據(jù)集合吧黄、動態(tài)數(shù)據(jù)集合
對于靜態(tài)數(shù)據(jù)部服，先排序，再取n/2+1拗慨。
對于動態(tài)數(shù)據(jù)饲宿，如果每次都排序厦酬，性能不好√毕耄可利用堆來實現(xiàn)仗阅。
定義兩個堆，一個大頂堆国夜，一個小頂堆减噪。大頂堆存儲前半數(shù)據(jù)，小頂堆存儲后半數(shù)據(jù)车吹，并且小頂堆的數(shù)據(jù)都大于大頂堆的數(shù)據(jù)筹裕。
初始化時窄驹，對現(xiàn)有數(shù)組進行排序朝卒，把前n/2（n/2+1）個數(shù)存儲到大頂堆里，把后n/2個數(shù)存儲到小頂堆中乐埠，中位數(shù)就是大頂堆的堆頂抗斤。
對于動態(tài)插入時，把數(shù)據(jù)跟大頂堆的堆頂進行比較丈咐，如果小于等于堆頂瑞眼，則插入到大堆頂。如果大于等于小堆頂?shù)亩秧斂醚罚瑒t插入小堆頂伤疙。最后再對大頂堆和小堆頂進行平衡，保證大頂堆是n/2（n/2+1)個數(shù)據(jù)辆影，小頂堆是n/2個數(shù)據(jù)徒像。
除了求中位數(shù)，還能求其他百分位的數(shù)據(jù)蛙讥，例如“99%響應時間”锯蛀。實際上中位數(shù)是求50%的數(shù)據(jù)，大堆頂和小堆頂各占50%键菱，對于“99%響應時間”這個問題，就是把大頂堆劃分為99%今布，小堆頂劃分為1%经备，其他實現(xiàn)跟中位數(shù)一樣。
時間復雜度：插入數(shù)據(jù)O(logn)侵蒙、返回堆頂O(1)
