排序-1億數據，1M記憶體，求TOP10，看看堆排序如何實現
- 2019 年 12 月 15 日
- 筆記
什麼是堆
堆是電腦程式中一種數據結構，堆是一種特殊的樹（完全二叉樹），完全二叉樹是說除了最後一層，其它層的節點必須是滿的(也就是說左右子樹的高度差不能超過一)，最後一層的節點必須靠左排列。堆中每個節點的值都必須大於等於或者小於左右子節點的值。只有符合這兩點的數據結構才是堆。
總結,符合如下兩個要求才是堆
- 是一個完全二叉樹
- 每個節點的值都必須大於等於或者小於左右子節點的值
將父節點值大於等於左右子節點的值的堆叫做大頂堆，將父節點值小於等於左右子節點的值的堆叫做小頂堆
我們看上面的圖分析得知：圖一是一個大頂堆，圖二是一個小頂堆，圖三，圖四不是一個完全二叉樹，因為最後一層的節點沒有靠左排列，圖五是一個完全二叉樹，但5這個節點大於它的左節點小於它的右節點，不符合堆的要求。
什麼是堆排序
堆排序是指利用堆這種數據結構設計的一種排序演算法，在說堆排序之前，我們首先看看如何用數組表述一個堆呢？看上面的第一幅圖（9，8，7，6），頂節點是9，它的左節點是8，右節點是7，在數組中9對應的下標是0，依次8對應1，7對應2，6對應3。
我們看圖能不能找到數組下標和堆中左右節點的一個規律，求9的左節點8等於0+1，右節點7等於0+2，8的左節點6等於1 * 2 +1，我們給上面的0+1,0+2的0都乘以2，可以得到一個公式，一個節點的左節點等於這個節點的下標乘以二加一，右節點等於這個節點的下標乘以二加二。
總結，在一個數組中，下標從零開始：
父節點的左兒子 = 父節點的下標 * 2 + 1 父節點的右兒子 = 父節點的下標 * 2 + 2
那麼我們如何對一個數組排序呢，比如數組[2,5,1,8,0] ？堆排序的過程分為兩步，第一步建堆，第二步堆化（也就是調整堆），我們通過程式碼實踐一下堆排序
我們看下面的圖來了解創建堆和調整對的整個過程，通過下圖相信大家一定會理解的，如下圖，第一行是創建堆的構成，後面兩行是調整堆的過程
小頂堆的過程其實也是一樣的，讀者們好好思考一下，可以自己試著實現一下
實現標題中提出的問題
文章標題中提出1億數據，1M記憶體，就TOP10，大頂堆的堆頂總是最大的，小頂堆的堆頂總是最小的，想一想此處我們應該用哪個呢？因為我們要求TOP10，我們一次性從文件中讀取10個元素，將這10個元素構建成一個小頂堆，此時堆頂是最小元素，然後我們依次從文件中讀取剩餘的元素，每次讀取一個，和堆頂元素比較，如果比堆頂的元素小，就直接捨棄，讀取下一個（堆頂已經最小了，比堆頂還小，那肯定不是TOP10）,如果比堆頂元素大，將堆頂元素替換成當前元素，此時堆頂元素就不是最小了，所以這時重新調整堆，使得堆頂的元素是這個10個元素中最小的，然後進行下一步，直到文件中所有數據都比較完成，這時整個堆就是TOP10，然後堆排序，依次輸出這10個元素。
堆的特性和應用場景
根據上面我們的分析，堆的一些特性總結如下：
- 堆分為大頂堆和小頂堆
- 大頂堆的堆頂元素時最大的
- 小頂堆的堆頂元素時最小的
- 堆本質也是一棵樹(完全二叉樹)
- 堆排序的時間複雜度是Nlog(N),空間複雜度是O(1)
基於堆的第二條和第三條特性，可以在實際場景中做很多有意義的事，如下舉例：
- 文章標題的問題，求topN，可以使用堆數據結構
- 優先順序隊列，優先順序最高或者最低的先出隊列，Jdk的優先順序隊列就是用堆實現的
- 合併有序的小文件（仔細想想這個過程）
- 高性能定時器，假設有一批任務，執行緒每隔很小的一個時間(1ms))掃描任務，看看有沒有需要執行的,這樣效率很低下，可以把這批任務構建成一個小頂堆，這樣執行緒只需要監控堆頂的任務。
- 求中位數，當數據是在不斷變化的時候，我們講數據較大的一部分放入大頂堆，較小的一部分放入小頂堆，當有新的元素進來時，如果比大頂堆的堆頂元素大，則放入大頂堆，如果比小頂堆的堆頂元素小，則放入小頂堆，最終兩個堆的元素個數可能差異比較大，這時做元素移動，直到兩個堆的元素個數相差不大於1，此時，如果數據總個數是偶數，則堆尾部的元素就是中位數,如果是奇數，則元素個數較多的那個堆的堆尾元素就是中位數.
讀者們可以好好思考一下上面的應用場景，可以看看源碼，或者自己實踐一下。
