作者 | 碼海
來源 | 碼海（ID：seaofcode）
堆是生產中非常重要也很實用的一種數據結構，也是面試中比如求 Top K 等問題的非常熱門的考點，本文旨在全面介紹堆的基本操作與其在生產中的主要應用，相信大家看了肯定收穫滿滿！
本文將會從以下幾個方面來講述堆:
生產中的常見問題
堆的定義
堆的基本操作
堆排序
堆在生產中應用
我們在生產中經常碰到以下常見的問題：
-
優先級隊列的應用場景很廣，它是如何實現的呢
如何求 Top K 問題
TP99 是生產中的一個非常重要的指標，如何快速計算
可能你已經猜到了，以上生產上的高頻問題都可以用堆來實現，所以理解堆及掌握其基本操作十分重要！接下來我們就來一步步地來了解堆及其相關操作，掌握了堆，上面三個生產上的高頻問題將不是問題。
堆的定義
堆有以下兩個特點：
堆是一顆完全二叉樹，這樣實現的堆也被稱為二叉堆
堆中節點的值都大於等於（或小於等於）其子節點的值，堆中如果節點的值都大於等於其子節點的值，我們把它稱為大頂堆，如果都小於等於其子節點的值，我們將其稱為小頂堆。
簡單回顧一下什麼是完全二叉樹，它的葉子節點都在最後一層，並且這些葉子節點都是靠左排序的。
從堆的特點可知，下圖中，1，2 是大頂堆，3 是小頂堆， 4 不是堆（不是完全二叉樹）
從圖中也可以看到，一組數據如果表示成大頂堆或小頂堆，可以有不同的表示方式，因為它只要求節點值大於等於（或小於等於）子節點值，未規定左右子節點的排列方式。
堆的底層是如何表示的呢，從以上堆的介紹中我們知道堆是一顆完全二叉樹，而完全二叉樹可以用數組表示：
如圖示：給完全二叉樹按從上到下從左到右編號，則對於任意一個節點來說，很容易得知如果它在數組中的位置為 i，則它的左右子節點在數組中的位置為 2i，2i + 1，通過這種方式可以定位到樹中的每一個節點，從而串起整顆樹。
一般對於二叉樹來說每個節點是要存儲左右子節點的指針，而由於完全二叉樹的特點（葉子節點都在最後一層，並且這些葉子節點都是靠左排序的），用數組來表示它再合適不過，用數組來存儲有啥好處呢，由於不需要存指向左右節點的指針，在這顆樹很大的情況下能省下很多空間！
堆的基本操作
堆有兩個基本的操作，構建堆（往堆中插入元素）與刪除堆頂元素，我們分別來看看這兩個操作
往堆中插入元素
往堆中插入元素後（如下圖示），我們需要繼續滿足堆的特性，所以需要不斷調整元素的位置直到滿足堆的特點為止（堆中節點的值都大於等於（或小於等於）其子節點的值）,我們把這種調整元素以讓其滿足堆特點的過程稱為堆化（heapify）
由於上圖中的堆是個大頂堆，所以我們需要調整節點以讓其符合大頂堆的特點。怎麼調整？不斷比較子節點與父節點，如果子節點大於父節點，則交換，不斷重複此過程，直到子節點小於其父節點。來看下上圖插入節點 11 後的堆化過程
這種調整方式是先把元素插到堆的最後，然後自下而上不斷比較子節點與父節點的值，我們稱之為由下而上的堆化。有了以上示意圖，不難寫出插入元素進行堆化的代碼：
public class Heap {
private int arr; // 堆是完全二叉樹，底層用數組存儲
private int capacity; // 堆中能存儲的最大元素數量
private int n; // 當前堆中元素數量
public Heap(int count) {
capacity = count;
arr = new int[capacity+1];
n = 0;
}
public void insert(int value) {
if (n >= capacity) {
// 超過堆大小了，不能再插入元素
return;
}
n++;
// 先將元素插入到隊尾中
arr[n] = value;
int i = n;
// 由於我們構建的是一個大頂堆，所以需要不斷調整以讓其滿足大頂堆的條件
while (i/2 > 0 && arr[i] > arr[i/2]) {
swap(arr, i, i/2);
i = i / 2;
}
}
}時間複雜度就是樹的高度，所以為 O(logn)。
刪除堆頂元素
由於堆的特點（節點的值都大於等於（或小於等於）其子節點的值），所以其根節點（堆項）要麼是所有節點中最大，要麼是所有節點中最小的，當刪除堆頂元素後，也需要調整子節點，以讓其滿足堆（大頂堆或小頂堆）的條件。
假設我們要操作的堆是大頂堆，則刪除堆頂元素後，要找到原堆中第二大的元素以填補堆頂元素，而第二大的元素無疑是在根節點的左右子節點上，假設是左節點，則用左節點填補堆頂元素之後，左節點空了，此時需要從左節點的左右節點中找到兩者的較大值填補左節點...，不斷迭代此過程，直到調整完畢，調整過程如下圖示：
但是這麼調整後，問題來了，如上圖所示，在最終調整後的堆中，出現了數組空洞，對應的數組如下：
怎麼解決？我們可以用最後一個元素覆蓋堆頂元素，然後再自上而下地調整堆，讓其滿足大頂堆的要求，這樣即可解決數組空洞的問題。
看了以上示意圖，代碼實現應該比較簡單，如下：
/**
* 移除堆頂元素
*/
public void removeTopElement {
if (n == 0) {
// 堆中如果沒有元素，也就是不存在移除堆頂元素的情況了
return;
}
int count = n;
arr[1] = arr[count];
--count;
heapify(1, count);
}
/**
* 自上而下堆化以滿足大頂堆的條件
*/
public void heapify(int index, int n) {
while (true) {
int maxValueIndex = index;
if (2 * index <= n && arr[index] < arr[2 * index]) {
// 左節點比其父節點大
maxValueIndex = 2 * index;
}
if (2 * index + 1 <= n && arr[maxValueIndex] < arr[2 * index + 1]) {
// 右節點比左節點或父節點大
maxValueIndex = 2 * index + 1;
}
if (maxValueIndex == index) {
// 說明當前節點值為最大值，無需再往下迭代了
break;
}
swap(arr, index, maxValueIndex);
index = maxValueIndex;
}
}
/**
* 交換數組第 i 和第 j 個元素
*/
public static void swap(int[] arr, int i, int j)
{
int temp = arr[i];
arr[i] = arr[j];
arr[j] = temp;
}
時間複雜度和插入堆中元素一樣，也是樹的高度，所以為 O(logn)。
堆排序
用堆怎麼實現排序？我們知道在大頂堆中，根節點是所有節點中最大的，於是我們有如下思路：
假設待排序元素個數為 n（假設其存在數組中），對這組數據構建一個大頂堆，刪除大頂堆的元素（將其與數組的最後一個元素進行交換），再對剩餘的 n-1 個元素構建大頂堆，再將堆頂元素刪除（將其與數組的倒數第二個元素交換），再對剩餘的 n-2 個元素構建大頂堆...，不斷重複此過程，這樣最終得到的排序一定是從小到大排列的，堆排序過程如下圖所示：
從以上的步驟中可以看到，重要的步驟就兩步，建堆（堆化，構建大頂堆）與排序。
先看下怎麼建堆，其實在上一節中我們已經埋下了伏筆，上一節我們簡單介紹了堆的基本操作，插入和刪除，所以我們可以新建一個數組，遍歷待排序的元素，每遍歷一個元素，就調用上一節我們定義的 insert(int value) 方法，這個方法在插入元素到堆的同時也會堆化調整堆為大頂堆，遍歷完元素後，最終生成的堆一定是大頂堆。
用這種方式生成的大頂堆空間複雜度是多少呢，由於我們新建了一個數組，所以空間複雜度是 O(n)，但其實堆排序是原地排序的（不需要任何額外空間），所以我們重點看下如何在不需要額外空間的情況下生成大頂堆。
其實思路很簡單，對於所有非葉子節點，自上而下不斷調整使其滿足大頂堆的條件（每個節點值都大於等於其左右節點的值）即可，遍歷到最後得到的堆一定是大頂堆！同時調整堆的過程中只是不斷交換數組裡的元素，沒有用到額外的存儲空間。
那麼非葉子節點的範圍是多少呢，假設數組元素為 n，則數組下標為 1 到 n / 2 的元素是非葉子節點。下標 n / 2 + 1 到 n 的元素是葉子節點。
畫外音：假設下標 n/2+1 的節點不是葉子節點，則其左子節點下標為 (n/2 + 1) * 2 = n + 2，超過了數組元素 n，顯然不符合邏輯，由此可以證明 n / 2 + 1 開始的元素一定是葉子節點。
示意圖如下：
如圖示：對每個非葉子節點自上而下調整後，最終得到大頂堆。
有了以上思路，不難寫出如下代碼:
/**
* 對 1 妻 n/2 的非葉子節點自上而下進行堆化，以構建大頂堆
*/
public void buildHeap {
for (int i = n/2; i > 0; i--) {
heapify(i);
}
}
這樣建堆的時間複雜度是多少呢，我們知道對每個元素進行堆化時間複雜度是 O(log n),那麼對 1 到 n/2 個元素進行堆化，則總的時間複雜度顯然是 O(n log n)（實際上如果詳細推導，時間複雜度是 O(n)，這裡不作展開，有興趣的同學建議查一下資料看下 O(n) 是怎麼來的）。
知道怎麼建堆，接下來排序就簡單了，對 n 個元素來說，只要移除堆頂元素（將其與最後一個元素交換），再對之前的 n-1 個元素堆化，再移除堆頂元素（將其與倒數第二個元素交換）...，不斷重複此過程即可，代碼如下:
/**
* 堆排序
*/
public void heapsort {
// 建堆
buildHeap;
int i = n;
while (true) {
if (i <= 1) {
break;
}
// 將堆頂元素放到第 i 個位置
swap(arr, 1, i);
i--;
// 重新對 1 到 i 的元素進行堆化，以讓其符合大頂堆的條件
heapify(1, i);
}
}
時間複雜度上文已經分析過了，就是 O(n log n)，居然和快排一樣快！但堆排序實際在生產中用得並不是很多，Java 默認的數組排序（Arrays.sort()）底層也是用的快排，時間複雜度和快排一樣快，為啥堆排序卻並不受待見呢。主要有以下兩個原因：
1、 快排在遞歸排序的過程中，都是拿 pivot 與相鄰的元素比較，會用到計算機中一個非常重要的定理：局部性原理，啥叫局部性原理，可以簡單理解為當 CPU 讀取到某個數據的時候，它認為這個數據附近相鄰的數據也有很大的概率會被用到，所以乾脆把被讀取到數據的附近的數據也一起加載到 Cache 中，這樣下次還需要再讀取數據進行操作時，就直接從 Cache 裡拿數據即可（無需再從內存裡拿了），數據量大的話，極大地提升了性能。堆排序無法利用局部性原理，為啥呢，我們知道在堆化的過程中，需要不斷比較節點與其左右子節點的大小，左右子節點也需要比較其左右節點。
如圖示：在對節點 2 自上而下的堆化中，其要遍歷數組中 4，5，9，10... 中的元素，這些元素並不是相鄰元素，無法利用到局部性原理來提升性能。
2、我們知道堆排序的一個重要步驟是把堆頂元素移除，重新進行堆化，每次堆化都會導致大量的元素比較，這也是堆排序性能較差的一個原因。
3、堆排序不是穩定排序，因為我們知道在堆化開始前要先把首位和末位元素進行交換，如果這兩元素值一樣，就可能改變他們原來在數組中的相對順序，而快排雖然也是不穩定排序，不過可以改進成穩定排序，這一點也是快排優於堆排序的一個重要的點。
堆在生產中應用
堆排序雖然不常用，但堆在生產中的應用還是很多的，這裡我們詳細來看堆在生產中的幾個重要應用：
1、 優先級隊列
我們知道隊列都是先進先出的，而在優先級隊列中，元素被賦予了權重的概念，權重高的元素優先執行，執行完之後下次再執行權重第二高的元素...，顯然用堆來實現優先級隊列再合適不過了，只要用一個大頂堆來實現優先級隊列即可，當權重最高的隊列執行完畢，將其移除（相當於刪除堆頂），再選出優先級第二高的元素（堆化讓其符合大頂堆 的條件），很方便，實際上我們查看源碼就知道， Java 中優先級隊列 PriorityQueue 就是用堆來實現的。
2、 求 TopK 問題
怎樣求出 n 個元素中前 K 個最大/最小的元素呢。假設我們要求前 K 個最大的元素，我們可以按如下步驟來做：
取 n 個元素的前 K 個元素構建一個小頂堆
遍歷第 K + 1 到 n 之間的元素，每一個元素都與小頂堆的堆頂元素進行比較，如果小於堆頂元素，不做任何操作，如果大於堆頂元素，則將堆頂元素替換成當前遍歷的元素，再堆化以讓其滿足小頂的要求，這樣遍歷完成後此小頂堆的所有元素就是我們要求的 TopK。
每個元素堆化的時間複雜度是 O(logK)，n 個元素時間複雜度是 O(nlogK)，還是相當給力的！
3、 TP99 是生產中的一個非常重要的指標，如何快速計算
先來解釋下什麼是 TP99，它指的是在一個時間段內（如5分鐘），統計某個接口（或方法）每次調用所消耗的時間，並將這些時間按從小到大的順序進行排序，取第99%的那個值作為 TP99 值，舉個例子， 假設這個方法在 5 分鐘內調用消耗時間為從 1 s 到 100 s 共 100 個數，則其 TP99 為 99，這個值為啥重要呢，對於某個接口來說，這個值越低，代表 99% 的請求都是非常快的，說明這個接口性能很好，反之，就說明這個接口需要改進，那怎麼去求這個值呢？
思路如下：
創建一個大頂堆和一個小頂堆，大頂堆的堆頂元素比小頂堆的堆頂元素更小，大頂堆維護 99% 的請求時間，小頂堆維護 1% 的請求時間
每產生一個元素（請求時間），如果它比大頂堆的堆頂元素小，則將其放入到大頂堆中，如果它比小頂堆的堆頂元素大，則將其插入到小頂堆中，插入後當然要堆化以讓其符合大小頂堆的要求。
上一步在插入的過程中需要注意一下，可能會導致大頂堆和小頂堆中元素的比例不為 99:1，此時就要做相應的調整，如果在將元素插入大頂堆之後，發現比例大於 99：1，將需將大頂堆的堆頂元素移到小頂堆中，再對兩個堆堆化以讓其符合大小頂堆的要求，同理，如果發現比例小於 99: 1，則需要將小頂堆的堆頂元素移到大頂堆來，再對兩者進行堆化。
以上的大小頂堆調整後，則大頂堆的堆頂元素值就是所要求的 TP99 值。
有人可能會說以上的這些應用貌似用快排或其他排序也能實現，沒錯，確實能實現，但是我們需要注意到，在靜態數據下用快排確實沒問題，但在動態數據上，如果每插入/刪除一個元素對所有的元素進行快排，其實效率不是很高，由於要快排要全量排序，時間複雜度是 O(nlog n)，而堆排序就非常適合這種對於動態數據的排序,對於每個新添加的動態數據，將其插入到堆中，然後進行堆化，時間複雜度只有 O(logK)
總結
堆是一種非常重要的數據結構，在對動態數據進行排序時性能很高，優先級隊列底層也是普遍採用堆來管理，所以掌握堆的基本操作十分重要。另外我們也知道了 Java 的優先級隊列（PriorityQueue）也是用堆來實現的，所以再次說明了掌握基本的數據結構非常重要，對於理解上層應用的底層實現十分有幫助！
參考：
https://time.geekbang.org/column/article/69913 堆和堆排序：為什麼說堆排序沒有快速排序快？
https://time.geekbang.org/column/article/70187 堆的應用：如何快速獲取到Top 10最熱門的搜索關鍵詞？
https://www.jianshu.com/p/6b526aa481b1
☞那些神一樣的程序員
☞漫畫：為什麼下載電影進度總是卡在99%就不動了？
☞任正非卸任上海華為董事；百度“雲手機”今日線上發佈；Inkscape 1.0&RC版發佈|極客頭條
☞通過Python代碼實現時間序列數據的統計學預測模型
☞比特幣當贖金，WannaRen勒索病毒二度來襲！
☞你知道嗎？其實Oracle直方圖自動統計算法存在這些缺陷！（附驗證步驟）
閱讀更多 CSDN程序人生 的文章
