一：如何理解“堆”

1，堆是一個完全二叉樹；
完全二叉樹要求除了最后一層，其他層的節點都是滿的，最后一層的節點都靠左排列。
2，堆中每個節點都必須大于等于（或小于等于）其子樹中每個節點的值。
堆中每個節點的值都大于等于（或者小于等于）其左右子節點的值。
3，對于每個節點的值都大于等于子樹中每個節點值的堆，叫作“大頂堆”。對于每個節點的值都小于等于子樹中每個節點值的堆，叫“小頂堆”。

二：如何實現“堆”

要實現一個堆，要先知道堆都支持哪些操作，已及如何存儲一個堆。
1，如何存儲一個堆：
完全二叉樹比較適合用數組來存儲。用數組來存儲完全二叉樹是非常節省存儲空間的。因為不需要存儲左右子節點的指針，單純地通過數組的下標，就可以找到一個節點的左右子節點和父節點。

2，往堆中插入一個元素
往堆中插入一個元素后，需要繼續滿足堆的兩個特性
（1）如果把新插入的元素放到堆的最后，則不符合堆的特性了，于是需要進行調整，讓其重新滿足堆的特性，這個過程叫做 堆化（heapify）
（2）堆化實際上有兩種，從下往上和從上往下
（3）從下往上的堆化方法：
堆化非常簡單，就是順著節點所在的路徑，向上或者向下，對比，然后交換。

public class Heap {private int[] a; // 數組，從下標1開始存儲數據private int n; // 堆可以存儲的最大數據個數private int count; // 堆中已經存儲的數據個數public Heap(int capacity) {a = new int[capacity + 1];n = capacity;count = 0;}public void insert(int data) {if (count >= n) return; // 堆滿了++count;a[count] = data;int i = count;while (i/2 > 0 && a[i] > a[i/2]) { // 自下往上堆化swap(a, i, i/2); // swap()函數作用：交換下標為i和i/2的兩個元素i = i/2;}}}

3，刪除堆頂元素 從上往下

（1）從堆的定義的第二條中，任何節點的值都大于等于（或小于等于）子樹節點的值，則堆頂元素存儲的就是堆中數據的最大值或最小值。
（2）假設是大頂堆，堆堆頂元素就是最大的元素，但刪除堆頂元素之后，就需要把第二大元素放到堆頂，那第二大元素肯定會出現在左右子節點中。然后在迭代地刪除第二大節點，以此類推，直到葉子節點被刪除。
但這種方式會使堆化出來的堆不滿足完全二叉樹的特性

（3）可以把最后一個節點放到堆頂，然后利用同樣的父子節點對比方法，對于不滿足父子節點大小關系的，互換兩個節點，并且重復進行這個過程，直到父子節點之間滿足大小關系為止，這是從上往下的堆化方法。

public class Heap {private int[] a; // 數組，從下標1開始存儲數據private int n; // 堆可以存儲的最大數據個數private int count; // 堆中已經存儲的數據個數public Heap(int capacity) {a = new int[capacity + 1];n = capacity;count = 0;}public void insert(int data) {if (count >= n) return; // 堆滿了++count;a[count] = data;int i = count;while (i/2 > 0 && a[i] > a[i/2]) { // 自下往上堆化swap(a, i, i/2); // swap()函數作用：交換下標為i和i/2的兩個元素i = i/2;}}}

一個包含n個節點的完全二叉樹，樹的高度不會超過log2n。堆化的過程是順著節點所在路徑比較交換的，所以堆化的時間復雜度跟樹的高度成正比，即O(log n)。插入數據和刪除堆頂元素的主要邏輯就是堆化，所以往堆中插入一個元素和刪除堆頂元素的時間復雜度都是O(log n)。

三：如何基于堆實現排序

排序方法有時間復雜度是O(n^2)的冒泡排序，插入排序，選擇排序，有時間復雜度是O（nlogn）的歸并排序，快速排序，線性排序。

借助堆這種數據結構實現的排序算法就叫作堆排序，這種排序方法的時間復雜度非常穩定，是O(nlogn)，并且它還是原地排序算法。
堆排序的過程大致分解為兩大步驟：建堆和排序

1. 建堆：

1，首先將數組原地建成一個堆。“原地”：是指不借助另一個數組，就在原地數組上操作。
2，建堆有兩種思路：
第一種：在堆中插入一個元素的思路。第一種建堆思路的處理過程是從前往后處理數組數據，并且每個數據插入堆中時，都是從下往上堆化。
盡管數組中包含n個數據，但是可以假設起初堆中只包含一個數據，就是下標為1的數據。然后，調用插入方法，將將下標從2到n的數據依次插入到堆中，這樣就將包含n個數據的數組，組織成了堆
第二種：是從后往前處理數組，并且每個數據都是從上往下堆化。

對下標從n/2開始到1的數據進行堆化，下標是n/2 + 1到n的節點，是葉子節點，不需堆化

private static void buildHeap(int[] a, int n) {for (int i = n/2; i >= 1; --i) {heapify(a, n, i);} }private static void heapify(int[] a, int n, int i) {while (true) {int maxPos = i;if (i*2 <= n && a[i] < a[i*2]) maxPos = i*2;if (i*2+1 <= n && a[maxPos] < a[i*2+1]) maxPos = i*2+1;if (maxPos == i) break;swap(a, i, maxPos);i = maxPos;} }

3，建堆的時間復雜度
每個節點堆化的時間復雜度是O(logn)，則n/2+1個節點堆化的總時間復雜度是O(n)。
①：因為葉子節點不需要堆化，所以需要堆化的節點從倒數第二層開始。每個節點堆化的過程中，需要比較和交換的節點個數，跟這個節點高度k成正比。

2. 排序：

建堆結束后，數組中的數據已是按照大頂堆的特性來組織的。數組中的第一個元素就是堆頂，也就是最大的元素。
將它和最后一個元素交換，最大元素就放到了下標為n的位置
這個過程有點類似“刪除堆頂元素”的操作，當堆頂元素移除后，把下標為n的元素放到堆頂，然后在通過堆化的方法，將剩下的n-1個元素重新構建成堆。堆化完成之后，在取堆頂元素，放到下標是n-1的位置，一直重復這個過程，直到最后堆中只剩下標為1的一個元素，排序工作就完成了。

// n表示數據的個數，數組a中的數據從下標1到n的位置。 public static void sort(int[] a, int n) {buildHeap(a, n);int k = n;while (k > 1) {swap(a, 1, k);--k;heapify(a, k, 1);} }

時間，空間復雜度，以及穩定性分析
①：整個堆排序的過程，都只需要極個別臨時存儲空間，所以堆排序是原地排序算法。
②：堆排序包括建堆和排序兩個操作，建堆過程的時間復雜度是O(n)，**排序過程的時間復雜度是O(nlogn),**所以堆排序的時間復雜度是O(nlogn)
③：堆排序不是穩定的排序算法，可能改變值相等的數據原始相對順序。

四：堆的應用

應用一：

<1>：優先級隊列
1，優先級隊列，數據的出隊順序不是先進先出，而是而是按照優先級來，優先級最高的，最先出隊。
2，實現一個優先級隊列方法很多，但是用堆來實現是最直接，最高效的，這是因為堆和優先級隊列非常相似。一個堆可以看作一個優先級隊列，很多時候，他們只是概念上的區分。往優先級隊列中插入一個元素，就相當于往堆中插入一個元素；從優先級隊列中取出優先級最高的元素，就相當于取出堆頂元素。
3，優先級隊列的應用廣泛，如赫夫曼編碼，圖的最短路徑，做小生成樹的算法等等

<2>：優先級隊列應用一：合并有序小文件
假設：有100個小文件，每個文件大小為100MB，每個文件中儲存的都是有序的字符串。現需要將這100個小文件合并成一個有序的大文件。
思路：

數組
1，整體思路有點像歸并排序中的合并函數，從100個文件中，各取第一個字符串，放入數組中，然后比較大小，把最小的那個字符串合并后的大文件中，并從數組中刪除。
2，假設，最小的字符串來自于13.txt這個文件，就再次從這個文件找那個取下一個字符串，放到數組中，重新比較大小，并且選擇最小的放入合并后的大文件，將它從數組中刪除。依次類推，直到所有的文件中的數據都放入到大文件為止。
3，使用數組來存儲從小文件中取出來的字符串，每次從數組中取最小字符串，都需要循環遍歷整個數組，效率不高。

優先隊列
4，可以用到優先級隊列，也可以說是堆。將從小文件中取出的字符串放入到小頂堆中，堆頂的元素就是優先級隊列隊首的元素，就是最小的字符串。
5，依次從小文件中取出下一個字符串，放入到堆中，循環這過程。
刪除堆頂數據和往堆中插入數據的時間復雜度都是O(logn)，n表示堆中的數據個數，這里就是100

<3>：優先隊列應用二：高性能定時器

假設：有一個定時器，定時器中維護了很多定時任務
1，每過1秒就掃描一遍任務列表做法太低效。原因1：任務的約定執行時間離當前時間可能還有很久，大量的掃描徒勞無功。原因2：每次都要掃描整個任務列表，若列表較大，會比較耗時。
2，針對這種文件，可用優先隊列來解決。按照任務設定的執行時間，將這些任務存儲在優先級隊列中，隊列首部（最小頂堆）存儲的是最先執行的任務。
3，這樣定時器就不用每隔一秒就掃描一遍任務列表了。它拿隊首任務的執行時間點，與當前時間點相減，即可得到一個時間間隔T。
4，當T秒時間過去后，定時器取優先級隊列中隊首的任務執行，然后在計算新的隊首任務的執行時間點和當前時間點的差值。
5，這樣定時器就不用間隔1秒就輪詢一次，也不用遍歷整個任務列表，性能就提高了。

應用二：利用堆求Top K

求Topk的問題可抽象成兩類：
1，針對靜態數據
可以維護一個大小為k的小頂堆，順序遍歷數組，從數組中取出數據與堆頂元素比較。如果堆頂元素大，就將堆頂元素刪除，并且將這個元素插入到堆中；如果比堆頂元素小則不做處理，繼續遍歷數組。這樣等數組中的數據都遍歷完之后，堆中的數據就是前k大數據了。
遍歷數據需要O(n)的時間復雜度，一次堆化操作需要O(logk)的時間復雜度，最壞情況下，n個元素都入堆一次，時間復雜度就是O(nlogk)。

2，針對動態數據求得Topk就是實時Topk。
一個數據集合有兩個操作，一個是添加數據，另一個詢問當前的前k大數據。
可以維護一直都維護一個k大小的小頂堆，當有數據被添加到集合時，就那它與堆頂的元素對對比。如果比堆頂元素大，就把堆頂元素刪除，并將這個元素插入到堆中，如果比堆頂元素小，這不處理。這樣，無論任何時候需要查詢當前的前k大數據，就都可以 立刻返回給他。

應用三：利用堆求中位數

1，對于一組靜態數據，中位數是固定的，可以先排序，第n/2個數據就是中位數。
2，對于動態數據集合，就無法先排序了，需要借助堆這種數據結構，我們不用排序，就可以非常高效的實現求中位數操作。
實現思路：
1，需要維護兩個堆，大頂堆中存儲前半部分數據，小頂堆中存儲后半部分數據，且小頂堆中的數據都大于大頂堆中的數據。
2，即：如果有n個數據，n是偶數，從小到大排序，那前n/2個數據存儲在大頂堆中，后n/2個數據存儲在小頂堆中。這樣，大頂堆中堆頂元素就是要找的中位數。
3，如果新加入的數據小于等于大頂堆的堆頂元素，就將這個數據插入到大頂堆；否則就插入小頂堆
4，當兩個堆中的數據量不服和中位數的約定時，就從一個堆中不停的將堆頂的元素移動到另一個堆，重新讓兩個堆中數據滿足上面的約定。

于是，可以利用兩個堆實現動態數據集合中求中位數的操作，插入數據因為涉及堆化，所以時間復雜度變成了O(logn)，但求中位數只需要返回大頂堆的堆頂元素就可以了，所以時間復雜度就是O(1)。

N 問題

假設現在我們有一個包含 10 億個搜索關鍵詞的日志文件，如何快速獲取到 Top 10 最熱門的搜索關鍵詞呢？
因為用戶搜索的關鍵詞，有很多可能都是重復的，所以我們首先要統計每個搜索關鍵詞出現的頻率。我們可以通過散列表、平衡二叉查找樹或者其他一些支持快速查找、插入的數據結構，來記錄關鍵詞及其出現的次數。
假設我們選用散列表。我們就順序掃描這 10 億個搜索關鍵詞。當掃描到某個關鍵詞時，我們去散列表中查詢。如果存在，我們就將對應的次數加一；如果不存在，我們就將它插入到散列表，并記錄次數為 1。以此類推，等遍歷完這 10 億個搜索關鍵詞之后，散列表中就存儲了不重復的搜索關鍵詞以及出現的次數。
假設我們選用散列表。我們就順序掃描這 10 億個搜索關鍵詞。當掃描到某個關鍵詞時，我們去散列表中查詢。如果存在，我們就將對應的次數加一；如果不存在，我們就將它插入到散列表，并記錄次數為 1。以此類推，等遍歷完這 10 億個搜索關鍵詞之后，散列表中就存儲了不重復的搜索關鍵詞以及出現的次數。
然后，我們再根據前面講的用堆求 Top K 的方法，建立一個大小為 10 的小頂堆，遍歷散列表，依次取出每個搜索關鍵詞及對應出現的次數，然后與堆頂的搜索關鍵詞對比。如果出現次數比堆頂搜索關鍵詞的次數多，那就刪除堆頂的關鍵詞，將這個出現次數更多的關鍵詞加入到堆中。
以此類推，當遍歷完整個散列表中的搜索關鍵詞之后，堆中的搜索關鍵詞就是出現次數最多的 Top 10 搜索關鍵詞了。

改進
10 億的關鍵詞還是很多的。我們假設 10 億條搜索關鍵詞中不重復的有 1 億條，如果每個搜索關鍵詞的平均長度是 50 個字節，那存儲 1 億個關鍵詞起碼需要 5GB 的內存空間，而散列表因為要避免頻繁沖突，不會選擇太大的裝載因子，所以消耗的內存空間就更多了。而我們的機器只有 1GB 的可用內存空間，所以我們無法一次性將所有的搜索關鍵詞加入到內存中。
我們在哈希算法那一節講過，相同數據經過哈希算法得到的哈希值是一樣的。我們可以根據哈希算法的這個特點，將 10 億條搜索關鍵詞先通過哈希算法分片到 10 個文件中。
具體可以這樣做：我們創建 10 個空文件 00，01，02，……，09。我們遍歷這 10 億個關鍵詞，并且通過某個哈希算法對其求哈希值，然后哈希值同 10 取模，得到的結果就是這個搜索關鍵詞應該被分到的文件編號。
對這 10 億個關鍵詞分片之后，每個文件都只有 1 億的關鍵詞，去除掉重復的，可能就只有 1000 萬個，每個關鍵詞平均 50 個字節，所以總的大小就是 500MB。1GB 的內存完全可以放得下。
我們針對每個包含 1 億條搜索關鍵詞的文件，利用散列表和堆，分別求出 Top 10，然后把這個 10 個 Top 10 放在一塊，然后取這 100 個關鍵詞中，出現次數最多的 10 個關鍵詞，這就是這 10 億數據中的 Top 10 最頻繁的搜索關鍵詞了。

有一個訪問量非常大的新聞網站，我們希望將點擊量排名 Top 10 的新聞摘要，滾動顯示在網站首頁 banner 上，并且每隔 1 小時更新一次。如果你是負責開發這個功能的工程師，你會如何來實現呢？
1，對每篇新聞摘要計算一個hashcode，并建立摘要與hashcode的關聯關系，使用map存儲，以hashCode為key，新聞摘要為值
2，按每小時一個文件的方式記錄下被點擊的摘要的hashCode
3，當一個小時結果后，上一個小時的文件被關閉，開始計算上一個小時的點擊top10
4，將hashcode分片到多個文件中，通過對hashCode取模運算，即可將相同的hashCode分片到相同的文件中
5，針對每個文件取top10的hashCode，使用Map<hashCode,int>的方式，統計出所有的摘要點擊次數，然后再使用小頂堆（大小為10）計算top10,
6，再針對所有分片計算一個總的top10,最后合并的邏輯也是使用小頂堆，計算top10
7，如果僅展示前一個小時的top10,計算結束
8，如果需要展示全天，需要與上一次的計算按hashCode進行合并，然后在這合并的數據中取top10
9，在展示時，將計算得到的top10的hashcode，轉化為新聞摘要顯示即可

在實際開發中，為什么快速排序要比堆排序性能好？
第一點，堆排序數據訪問的方式沒有快速排序友好。
對于快速排序來說，數據是順序訪問的。而對于堆排序來說，數據是跳著訪問的。 比如，堆排序中，最重要的一個操作就是數據的堆化。比如下面這個例子，對堆頂節點進行堆化，會依次訪問數組下標是 1，2，4，8 的元素，而不是像快速排序那樣，局部順序訪問，所以，這樣對 CPU 緩存是不友好的。
第二點，對于同樣的數據，在排序過程中，堆排序算法的數據交換次數要多于快速排序。
我們在講排序的時候，提過兩個概念，有序度和逆序度。對于基于比較的排序算法來說，整個排序過程就是由兩個基本的操作組成的，比較和交換（或移動）。快速排序數據交換的次數不會比逆序度多。但是堆排序的第一步是建堆，建堆的過程會打亂數據原有的相對先后順序，導致原數據的有序度降低。比如，對于一組已經有序的數據來說，經過建堆之后，數據反而變得更無序了。

筆記整理來源： 王爭 數據結構與算法之美

總結

以上是生活随笔為你收集整理的【数据结构与算法】堆的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。