我的博客地址：https://rebornc.github.io/2018/11/15/%E5%A0%86%E6%8E%92%E5%BA%8F%E4%B8%8E%E6%B5%B7%E9%87%8FTopK%E9%97%AE%E9%A2%98/

排序算法是個老生常談的問題，筆試要考，面試也問，不過翻來覆去也就那幾個花樣吧。大概理解一下各個算法的原理，記下表格里的數據，然后再試試手撕代碼，基本上就沒問題了。

從表格里可以看出，堆排序是一個時間和空間復雜度都比較優(yōu)秀的算法，至于它的原理，看懂是肯定能輕易看懂的，但是我總覺得如果你不自己親手寫一遍，就很容易忘記。并且，用遞歸的話，代碼也是很簡短的，還沒寫過的同學，不妨自己試著敲一下吧hhh。

因為太久沒寫博客了覺得不能這么頹廢下去，所以今天打算好好整理堆排序的相關知識點，同時講一下面試時經常會被問到的TopK問題。

堆排序

1. 什么是堆

堆（heap）是一種數據結構，也被稱為優(yōu)先隊列（priority queue）。隊列中允許的操作是先進先出（FIFO），在隊尾插入元素，在隊頭取出元素。而堆也是一樣，在堆底插入元素，在堆頂取出元素，但是堆中元素的排列不是按照到來的先后順序，而是按照一定的優(yōu)先順序排列的。這個優(yōu)先順序可以是元素的大小或者其他規(guī)則。
而二叉堆是一種特殊的堆，它是完全二元樹（二叉樹）或者是近似完全二元樹（二叉樹）。二叉堆有兩種：最大堆和最小堆。最大堆：父結點的鍵值總是大于或等于任何一個子節(jié)點的鍵值；最小堆：父結點的鍵值總是小于或等于任何一個子節(jié)點的鍵值。如下圖。

2. 堆排序的原理

堆排序（HeapSort）是指利用堆這種數據結構所設計的一種排序算法。它的關鍵在于建堆和調整堆。步驟主要如下：

• 創(chuàng)建一個堆；
• 把堆首（最大值）和堆尾互換；
• 把堆的尺寸縮小1，并調整堆，把新的數組頂端數據調整到相應位置；
• 重復步驟 2，直到堆的尺寸為1，此時排序結束。

當然，光看文字肯定不能很直觀地理解，我們跟著圖示來學習吧。
現(xiàn)在，我們有一個待排序的數組 {2, 4, 3, 7, 5, 8}，我們通過構建最大堆的方法來排序。

• 步驟說明如下：
  1. 將待排序的數組視作完全二叉樹，按層次遍歷。
  2. 找到二叉樹的最后一個非葉子節(jié)點，也就是最后一個節(jié)點的父節(jié)點。即是 (len-1)/2 索引在的位置。如果其子節(jié)點的值大于其本身的值，則把它和較大子節(jié)點進行交換，即將數字3和8交換。如果并沒有子節(jié)點大于它，則無需交換。
  3. 循環(huán)遍歷，繼續(xù)處理前一個節(jié)點，由于此時 4<7 ，因此再次交換。
  4. 循環(huán)遍歷，繼續(xù)處理前一個節(jié)點，由于此時 2<8 ，因此再次交換。注意：如果某個節(jié)點和它的某個子節(jié)點交換后，該子節(jié)點又有子節(jié)點，系統(tǒng)還需要再次對該子節(jié)點進行判斷，做相同處理。
  5. 遍歷完成后得到一個最大堆。將每次堆排序得到的最大元素與當前規(guī)模的數組最后一個元素（假設下標為i）交換，然后再繼續(xù)調整前 i - 1 的數組。遍歷終止之后，得到一個自小到大的排序數組。

C++代碼實現(xiàn)如下

void adjust(vector<int> &arr, int index, int len) {
    int left = 2 * index + 1;
    int right = 2 * index + 2;
    int max_index = index;
    if (left < len && arr[left] > arr[max_index]) max_index = left;
    if (right < len && arr[right] > arr[max_index]) max_index = right;
    if (max_index != index) {
        swap(arr[max_index], arr[index]);
        adjust(arr, max_index, len); // 繼續(xù)調整子節(jié)點
    }
}
void heapSort(vector<int> &arr, int len) {
    // 將數組進行堆排序
    for (int i = len / 2 - 1; i >= 0; i--) {
        adjust(arr, i, len);
    }
    // 將每次堆排序得到的最大元素與當前規(guī)模的數組最后一個元素交換
    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的數組，然后遍歷后續(xù)的數字，進行比較后決定是否替換。這時候堆排序就派上用場了。我們可以將前K個數字建立為一個最?。ù螅┒眩绻且∽畲蟮腒個數，則在后續(xù)遍歷中，將數字與最小堆的堆頂數字進行比較，若比它大，則進行替換，然后再重新調整為最大堆。整個過程直至所有數字遍歷完為止。時間復雜度為O(n*log?K)，空間復雜度為K。

C++代碼實現(xiàn)如下

class Solution {
public:
    void adjust(vector<int> &arr, int index, int len) {
        int left = 2 * index + 1;
        int right = 2 * index + 2;
        int max_index = index;
        if (left < len && arr[left] > arr[max_index]) max_index = left;
        if (right < len && arr[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<int> &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<int> GetLeastNumbers_Solution(vector<int> input, int k) {
        if (k <= 0 || k > input.size()) {
            vector<int> nullVec;
            return nullVec;
        }
        // 因為要取最小的k個數，所以取前k個數字構建一個最大堆
        // 相反，如果是取最大的k個數，則構建一個最小堆
        vector<int> sortedArray(input.begin(), input.begin() + k);
        heapSort(sortedArray, k);
        // 將后面的數字與這個構建好的二叉堆進行比較 
        for (int i = k; i < input.size(); i++) {
            if (input[i] < sortedArray[0]) {
                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;
    }
};

相似的TopK問題還有：

• 有10000000個記錄，這些查詢串的重復度比較高，如果除去重復后，不超過3000000個。一個查詢串的重復度越高，說明查詢它的用戶越多，也就是越熱門。請統(tǒng)計最熱門的10個查詢串，要求使用的內存不能超過1GB。
• 有10個文件，每個文件1GB，每個文件的每一行存放的都是用戶的query，每個文件的query都可能重復。按照query的頻度排序。
• 有一個1GB大小的文件，里面的每一行是一個詞，詞的大小不超過16個字節(jié)，內存限制大小是1MB。返回頻數最高的100個詞。
• 提取某日訪問網站次數最多的那個IP。
• 10億個整數找出重復次數最多的100個整數。
• 搜索的輸入信息是一個字符串，統(tǒng)計300萬條輸入信息中最熱門的前10條，每次輸入的一個字符串為不超過255B，內存使用只有1GB。
• 有1000萬個身份證號以及他們對應的數據，身份證號可能重復，找出出現(xiàn)次數最多的身份證號。
• 等等...

對于這類問題，比如上面第1個，可以先利用hash表將查詢串存儲并計數，然后再構建最小堆，將查詢串的個數進行比較從而得到結果。核心思想都是一樣的。

今天就先寫到這里吧，困了睡覺去 Orz