排序算法是個老生常談的問題，筆試要考，面試也問，不過翻來覆去也就那幾個花樣吧。大概了解一下各個算法的原理，記下表格裡的資料，然後再試試手撕代碼，基本上就沒問題了。
從表格裡可以看出，堆排序是一個時間和空間複雜度都比較優秀的算法，至于它的原理，看懂是肯定能輕易看懂的，但是我總覺得如果你不自己親手寫一遍，就很容易忘記。并且，用遞歸的話，代碼也是很簡短的，還沒寫過的同學，不妨自己試着敲一下吧hhh。
因為太久沒寫部落格了覺得不能這麼頹廢下去，是以今天打算好好整理堆排序的相關知識點，同時講一下面試時經常會被問到的TopK問題。
堆排序
1. 什麼是堆
堆(heap)是一種資料結構，也被稱為優先隊列(priority queue)。隊列中允許的操作是先進先出(FIFO)，在隊尾插入元素，在隊頭取出元素。而堆也是一樣，在堆底插入元素，在堆頂取出元素，但是堆中元素的排列不是按照到來的先後順序，而是按照一定的優先順序排列的。這個優先順序可以是元素的大小或者其他規則。
而二叉堆是一種特殊的堆，它是完全二進制樹(二叉樹)或者是近似完全二進制樹(二叉樹)。二叉堆有兩種：最大堆和最小堆。最大堆：父結點的鍵值總是大于或等于任何一個子節點的鍵值；最小堆：父結點的鍵值總是小于或等于任何一個子節點的鍵值。如下圖。
2. 堆排序的原理
堆排序(HeapSort)是指利用堆這種資料結構所設計的一種排序算法。它的關鍵在于建堆和調整堆。步驟主要如下：建立一個堆；
把堆首(最大值)和堆尾互換；
把堆的尺寸縮小1，并調整堆，把新的數組頂端資料調整到相應位置；
重複步驟 2，直到堆的尺寸為1，此時排序結束。
當然，光看文字肯定不能很直覺地了解，我們跟着圖示來學習吧。
現在，我們有一個待排序的數組 {2, 4, 3, 7, 5, 8}，我們通過建構最大堆的方法來排序。
步驟說明如下：
1. 将待排序的數組視作完全二叉樹，按層次周遊。
2. 找到二叉樹的最後一個非葉子節點，也就是最後一個節點的父節點。即是 (len-1)/2 索引在的位置。如果其子節點的值大于其本身的值，則把它和較大子節點進行交換，即将數字3和8交換。如果并沒有子節點大于它，則無需交換。
3. 循環周遊，繼續處理前一個節點，由于此時 4<7 ，是以再次交換。
4. 循環周遊，繼續處理前一個節點，由于此時 2<8 ，是以再次交換。注意：如果某個節點和它的某個子節點交換後，該子節點又有子節點，系統還需要再次對該子節點進行判斷，做相同處理。
5. 周遊完成後得到一個最大堆。将每次堆排序得到的最大元素與目前規模的數組最後一個元素(假設下标為i)交換，然後再繼續調整前 i - 1 的數組。周遊終止之後，得到一個自小到大的排序數組。
C++代碼實作如下void adjust(vector &arr, int index, int len) { int left = 2 * index + 1; int right = 2 * index + 2; int max_index = index; if (left arr[max_index]) max_index = left; if (right arr[max_index]) max_index = right; if (max_index != index) {
swap(arr[max_index], arr[index]);
adjust(arr, max_index, len); // 繼續調整子節點
}
}void heapSort(vector &arr, int len) { // 将數組進行堆排序
for (int i = len / 2 - 1; i >= 0; i--) {
adjust(arr, i, len);
} // 将每次堆排序得到的最大元素與目前規模的數組最後一個元素交換
for (int i = len - 1; i >= 1; i--) {
swap(arr[0], arr[i]);
adjust(arr, 0, i);
}
}
海量TopK問題
劍指Offer有這樣一道題，求最小的K個數，題目描述：輸入n個整數，找出其中最小的K個數。例如輸入 4，5，1，6，2，7，3，8 這8個數字，則最小的4個數字是 1，2，3，4。
而在面試的時候，我們也可能遇到這樣的問題：有一億個浮點數，如何找出其中最大的10000個？
這類問題我們把稱為TopK問題：指從大量資料(源資料)中擷取最大(或最小)的K個資料。
最容易想到的方法當然是全部排序再進行查找，然而時間複雜度怎麼也要O(nlog₂n)，當n極其大時，該算法占用的記憶體也emmm。而我們題目所要求傳回的隻是前K個資料，是以沒必要全部排序，做那麼多無用功。我們可以先取下标 0~k-1 的局部數組，用它來維護一個大小為K的數組，然後周遊後續的數字，進行比較後決定是否替換。這時候堆排序就派上用場了。我們可以将前K個數字建立為一個最小(大)堆，如果是要取最大的K個數，則在後續周遊中，将數字與最小堆的堆頂數字進行比較，若比它大，則進行替換，然後再重新調整為最大堆。整個過程直至所有數字周遊完為止。時間複雜度為O(n*log₂K)，空間複雜度為K。
C++代碼實作如下class Solution {public: void adjust(vector &arr, int index, int len) { int left = 2 * index + 1; int right = 2 * index + 2; int max_index = index; if (left arr[max_index]) max_index = left; if (right arr[max_index]) max_index = right; if (max_index != index) {
swap(arr[max_index], arr[index]);
adjust(arr, max_index, len);
}
}
void heapSort(vector &arr, int len) { for (int i = len / 2 - 1; i >= 0; i--) {
adjust(arr, i, len);
} // for (int i = len - 1; i >= 1; i--) {
// swap(arr[0], arr[i]);
// adjust(arr, 0, i);
// }
} vector GetLeastNumbers_Solution(vector input, int k) { if (k <= 0 || k > input.size()) { vector nullVec; return nullVec;
} // 因為要取最小的k個數，是以取前k個數字建構一個最大堆
// 相反，如果是取最大的k個數，則建構一個最小堆
vector sortedArray(input.begin(), input.begin() + k);
heapSort(sortedArray, k); // 将後面的數字與這個建構好的二叉堆進行比較
for (int i = k; i
sortedArray[0] = input[i];
adjust(sortedArray, 0, k);
}
} for (int i = k - 1; i >= 1; i--) {
swap(sortedArray[0], sortedArray[i]);
adjust(sortedArray, 0, i);
} return sortedArray;
}
};
作者：白夜叉小分隊
連結：https://www.jianshu.com/p/c8feaee16cae