一、什么是堆

1.1 堆的定義

堆是一個(gè)完全二叉樹；

堆中的每一個(gè)節(jié)點(diǎn)的值都必須大于等于（大頂堆）or小于等于（小頂堆）其子樹中的每個(gè)節(jié)點(diǎn)的值；

1.2 堆上的操作

• 堆的存儲
• 我們在前面二叉樹的學(xué)習(xí)中就知道，完全二叉樹最理想的存儲方式便是數(shù)組，省去了左右節(jié)點(diǎn)的指針空間，而且不會造成很大的浪費(fèi)。比如，節(jié)點(diǎn)位置為i，那么其左子樹就存放在2i的位置，右子樹就存放在2i+1的位置，其父節(jié)點(diǎn)在i/2的位置，向上向下索引都很快捷。
• 插入元素
• 我們一般都將待插入的數(shù)據(jù)作為一個(gè)節(jié)點(diǎn)放到當(dāng)前堆的最后面，然后自下而上進(jìn)行堆化操作。

在堆的最后面插入一個(gè)節(jié)點(diǎn)

自下而上進(jìn)行堆化

• 刪除堆頂元素
• 堆一般都是進(jìn)行刪除堆頂元素，因?yàn)槎秧敳皇亲畲笾稻褪亲钚≈?。一般不會刪除非堆頂元素，這是堆這種數(shù)據(jù)結(jié)構(gòu)的特性決定的。
• 我們先將堆中的最后一個(gè)元素賦值給堆頂元素，然后再刪除最后一個(gè)元素，最后再進(jìn)行自上而下的堆化操作。

刪除堆頂元素的堆化操作

在如上插入和刪除堆頂元素的操作中，主要的時(shí)間消耗都在堆化這個(gè)過程中，堆化操作需要比較和交換的次數(shù)最大不會超過樹的高度，而前面我們說過，完全二叉樹的高度是2的對數(shù)，因此插入和刪除堆頂元素操作的時(shí)間復(fù)雜度是O(logn)。

二、 堆排序

給定一個(gè)數(shù)組，其中的元素都是無序雜亂的，我們怎么對它進(jìn)行堆排序呢？

2.1 建堆

首先，我們需要將該數(shù)組建立為一個(gè)大頂堆（小頂堆），通常有以下兩種建堆的方法：

• 自上而下
• 把下標(biāo)為1的元素作為原始堆，然后從下標(biāo)2開始直到n，依次插入前面的堆中，就像前面講的插入元素操作一樣，不斷地進(jìn)行堆化，然后形成一個(gè)大頂堆；其時(shí)間復(fù)雜度為O(nlogn)，不夠好。
• 自下而上
• 我們注意到，在完全二叉樹中，最后一個(gè)元素的下標(biāo)除以2就能得到最后一個(gè)非葉子節(jié)點(diǎn)元素的下標(biāo)n/2，光是葉子節(jié)點(diǎn)是無法進(jìn)行堆化的，因此我們從n/2開始往前一直到下標(biāo)為1為止不斷進(jìn)行堆化，然后形成一個(gè)大頂堆；此過程就類似刪除堆頂元素之后的堆化過程；其時(shí)間復(fù)雜度為O(n)，優(yōu)于第一種。

建堆時(shí)自下而上進(jìn)行堆化的過程

2.2 排序

經(jīng)過上一步的建堆操作，我們得到了一個(gè)大頂堆，但是數(shù)組中的數(shù)據(jù)看上去仍然是無序的，我們需要基于這個(gè)大頂堆把數(shù)組排下序。

首先從堆頂取出元素，這個(gè)元素肯定是最大的，把它和數(shù)組最后一個(gè)元素進(jìn)行交換，放到位置n，然后堆中剩下的元素不斷地進(jìn)行堆化，并始終取堆頂元素依次放到n-1,n-2,n-3的位置上，當(dāng)堆中只剩最后一個(gè)元素的時(shí)候，此時(shí)數(shù)組就是一個(gè)有序數(shù)列了。

堆排序的過程示意

堆排序的過程中，我們需要對n個(gè)元素進(jìn)行堆化操作，每次堆化操作時(shí)間復(fù)雜度取決于完全二叉樹的高度，所以最終得到堆排序的時(shí)間復(fù)雜度為O(nlogn)。

堆排序不需要借助很多的額外存儲空間，因此它屬于原地排序；

堆排序過程中會可能改變相同值的位置，所以不是穩(wěn)定的排序算法；

2.3 堆排序和快速排序的比較

雖然堆排序和快速排序時(shí)間的時(shí)間復(fù)雜度都是O(nlogn)，但通常都認(rèn)為堆排序的性能是比不上快速排序的。

• 堆排序的堆化過程中，在比較和交換元素時(shí)，讀取的數(shù)據(jù)并不是局部順序的；快速排序就是局部順序的；所以快速排序更加顯得CPU緩存友好，性能也會相對較好；
• 對于同樣的數(shù)列，堆排序數(shù)據(jù)的交換次數(shù)要多于快速排序；

三、堆排序的應(yīng)用

3.1 堆排序

如上已經(jīng)講解過了。

3.2 優(yōu)先級隊(duì)列

優(yōu)先級隊(duì)列中，數(shù)據(jù)的出隊(duì)不是按照入隊(duì)先后來決定的，而是按照優(yōu)先級來的，優(yōu)先級高（低）的就先出隊(duì)，實(shí)現(xiàn)優(yōu)先級隊(duì)列的方法有很多，但是其中使用堆來實(shí)現(xiàn)是最為快捷高效的。比如Java中的PriorityQueue。

場景一：合并有序小文件

假設(shè)我們有n個(gè)小文件，每個(gè)大小為100MB，每個(gè)文件中存放的都是有序的字符串，我們?nèi)绾伟堰@n個(gè)小文件中的字符串有序地全都合并到一個(gè)大文件中呢？

這里有兩個(gè)方法：

• 按照歸并排序中的合并思路
• 設(shè)置n個(gè)指針各自指向每個(gè)文件的第一個(gè)字符串，將它們都加載到一個(gè)大小為n的數(shù)組中;
• 然后對數(shù)組進(jìn)行遍歷尋找最小元素，時(shí)間復(fù)雜度為O(n)；并從數(shù)組中取出最小元素放到大文件中，將該元素從數(shù)組中刪除；
• 將該元素來源的小文件中的指針移向下一位取出元素放到數(shù)組中，然后重復(fù)第二步；
• 使用小頂堆
• 設(shè)置n個(gè)指針各自指向每個(gè)文件的第一個(gè)字符串，將它們都加載到一個(gè)小頂堆中，初始是一個(gè)建堆的過程；
• 取出堆頂元素放到大文件中，并將該元素從小頂堆的堆頂刪除，小頂堆會自動(dòng)進(jìn)行堆化；
• 將該元素來源的小文件中的指針移向下一位取出元素插入小頂堆中，小頂堆會自動(dòng)進(jìn)行堆化，然后重復(fù)第二步；
• 我們可以看到，這兩種方法的區(qū)別在于，前者需要每次遍歷數(shù)組找到最小值，后者則是有刪除和插入兩個(gè)堆化的過程。堆化過程的時(shí)間復(fù)雜度為O(logn)，明顯比遍歷數(shù)組的O(n)要好，所以方法二更加高效。

場景二：實(shí)現(xiàn)高性能定時(shí)器

假設(shè)我們使用定時(shí)器設(shè)置了很多個(gè)待執(zhí)行的任務(wù)，那么如何實(shí)現(xiàn)定時(shí)觸發(fā)這些提前設(shè)定好的任務(wù)呢？

這里說三個(gè)方法：

• 程序每隔一段很小的時(shí)間（比如1秒）就進(jìn)行任務(wù)掃描，找到最近要執(zhí)行的任務(wù)進(jìn)行執(zhí)行，這種方法其實(shí)就是每1秒都要去尋找最小值，每次的時(shí)間復(fù)雜都是O(n)，而且，假設(shè)最近一個(gè)任務(wù)是定在2小時(shí)候執(zhí)行的，那么這2小時(shí)內(nèi)，掃描程序都是白執(zhí)行的，浪費(fèi)資源。這種方法并不推薦。
• 維護(hù)一個(gè)有序列表，比如使用快速排序，只要記住最小值的執(zhí)行時(shí)間即可，等到了那個(gè)時(shí)間點(diǎn)程序再執(zhí)行，如此掃描程序就不用一直去掃描了。
• 使用小頂堆來維護(hù)任務(wù)列表，記住堆頂任務(wù)的執(zhí)行時(shí)間，等到了那個(gè)時(shí)間點(diǎn)程序再執(zhí)行，如此掃描程序就不用一直去掃描了。
• 方法2和方法3其實(shí)是類似的，關(guān)鍵在于采取什么樣的數(shù)據(jù)結(jié)構(gòu)和算法來獲取最小值。如果存在中途插入或者取消任務(wù)的情況，對于方法2來說，插入一個(gè)元素到有序列表中和從有序列表中刪除一個(gè)給定元素時(shí)間復(fù)雜度是多少呢？假設(shè)我們采用效率最高的二分查找，那么是O(logn)，但是插入和刪除元素是要搬移元素的，這個(gè)時(shí)間是O(n)，所以總的下來就是O(n)；如果使用方法3，那么無論插入還是刪除元素，都是一個(gè)堆化的過程，時(shí)間復(fù)雜度為O(logn)，所以方法3中使用堆更加高效。

3.3 求解Top-k問題

假設(shè)存量數(shù)據(jù)量為n，我們需要從n中找到Top-k的元素，并且針對不斷添加進(jìn)來的數(shù)據(jù)，我們都要獲取最新的Top-k元素，這種問題應(yīng)該怎么處理呢？

• 先從n中取出前k個(gè)元素，組成一個(gè)小頂堆，此時(shí)堆頂元素是最小的，我們從K+1個(gè)元素開始，和堆頂元素進(jìn)行比較，如果比堆頂元素小，那么不做處理，繼續(xù)下一個(gè)；如果比堆頂元素大，那么把堆頂元素刪除，并插入k+1這個(gè)元素；等到n個(gè)元素全部遍歷完，那么小頂堆中的k個(gè)元素就是Top-k數(shù)據(jù)了；
• 對于外部不斷添加進(jìn)來的數(shù)據(jù)其實(shí)思路是一樣的，把它當(dāng)成數(shù)據(jù)源，不斷地和堆頂元素比較，重復(fù)上面的步驟操作即可。

時(shí)間主要耗費(fèi)在一開始k個(gè)元素的初始建堆O(logk)上，還有刪除堆頂元素和插入新元素時(shí)的堆化O(logk)上；所以，總的時(shí)間復(fù)雜度應(yīng)該為O(nlogk)，比使用排序來獲取Top-k的O(nlogn)還是要高效的。

3.4 求解中位數(shù)

對于一個(gè)無序的數(shù)列，怎么求出它的中位數(shù)呢？這要看數(shù)列是靜態(tài)的還是動(dòng)態(tài)的。

如果是靜態(tài)的數(shù)列，那么我們先進(jìn)行排序，比如快速排序O(nlogn)，然后如果總數(shù)是奇數(shù)，那么中位數(shù)就在n/2+1的位置上；如果總數(shù)是偶數(shù)，那么中位數(shù)有兩個(gè)，在n/2和n/2+1的位置上，隨便取一個(gè)即可。總的時(shí)間復(fù)雜度就是排序算法的時(shí)間復(fù)雜度O(nlogn)。

那如果是動(dòng)態(tài)數(shù)列呢，我們需要維護(hù)數(shù)列的有序性，那么勢必要對新插入或者需要?jiǎng)h除的數(shù)據(jù)進(jìn)行查找，時(shí)間復(fù)雜度為O(n)，還有數(shù)據(jù)搬移的O(n)，所以就會變得很低效，我們需要使用堆來解決這個(gè)問題。

我們先將已有數(shù)據(jù)排序，然后維護(hù)一個(gè)大頂堆和一個(gè)小頂堆，其中小頂堆存放最大的n/2個(gè)數(shù)據(jù)，堆頂元素是這n/2中最小的，大頂堆存放剩下的元素，堆頂元素是最大的。此時(shí)，中位數(shù)就是大頂堆的堆頂元素。

當(dāng)動(dòng)態(tài)數(shù)據(jù)添加進(jìn)來時(shí)，我們將待添加元素和大頂堆的堆頂元素進(jìn)行比較，如果小于等于，那么就插入大頂堆中；否則就和小頂堆的堆頂元素比較，如果大于等于，就插入小頂堆中。此時(shí)，如果小頂堆中的個(gè)數(shù)超過了n/2，就需要不斷地取出堆頂元素插入到大頂堆中，直至個(gè)數(shù)為n/2；如果小頂堆中的個(gè)數(shù)小于n/2，就需要不斷地取出大頂堆的堆頂元素插入到小頂堆中，直至小頂堆個(gè)數(shù)為n/2；

動(dòng)態(tài)數(shù)列使用堆求解中位數(shù)過程示意

通過如上的過程，我們每次從大頂堆堆頂取出來的元素就是整個(gè)數(shù)列的中位數(shù)。整個(gè)過程的時(shí)間復(fù)雜度是多少呢？一開始初始化時(shí)的排序和建堆，由于數(shù)據(jù)比較少，可以算作常量；后續(xù)動(dòng)態(tài)數(shù)據(jù)的插入或者刪除，就是一個(gè)堆化的過程，時(shí)間復(fù)雜度為O(logn)；大頂堆和小頂堆之間元素個(gè)數(shù)的調(diào)整不會有很多元素，所以也算作常數(shù)；因此，總的時(shí)間復(fù)雜度就是O(logn)。

既然動(dòng)態(tài)數(shù)列求解中位數(shù)使用堆比較好，為什么靜態(tài)數(shù)列求解中位數(shù)不使用堆，而是排序呢？靜態(tài)數(shù)列也可以使用如上堆的方案進(jìn)行求解中位數(shù)，但是時(shí)間復(fù)雜度也是O(nlogn)，和排序是一樣的，但是排序明顯更加地簡單，因此推薦使用排序的方案。

3.5 求解百分位數(shù)

求解中位數(shù)的問題其實(shí)就是求解百分位數(shù)問題的一種特殊情況， 中位數(shù)可以理解為百分位為50%，所以把中位數(shù)問題一般化的話，那么問題就是求解任意百分位數(shù)的問題。

思路和上述求解百分位是一樣的，比如我們要求解90%百分位的數(shù)，那么大頂堆中需要存放90%的數(shù)據(jù)，小頂堆中存放10%的數(shù)據(jù)，當(dāng)動(dòng)態(tài)地增加時(shí)需要依次和大頂堆、小頂堆的堆頂元素進(jìn)行比較以決定插入到哪個(gè)堆中；如果插入或者刪除后，小頂堆中的數(shù)據(jù)占比不是10%了，就需要和大頂堆進(jìn)行數(shù)據(jù)的交互以保證小頂堆數(shù)據(jù)的占比，如此才能保證大頂堆的堆頂元素就是我們需要的百分位數(shù)據(jù)。?