堆排序是壹種原地的、時間復雜度為 O(nlogn) 的排序算法。
堆是壹種特殊的樹。
只要滿足這兩點，它就是壹個堆：
對於每個節點的值都大於等於子樹中每個節點值的堆，我們叫做 “大頂堆” 。對於每個節點的值都小於等於子樹中每個節點值的堆，我們叫做 “小頂堆” 。
完全二叉樹比較適合用數組來存儲。用數組來存儲完全二叉樹是非常節省存儲空間的。下標可以直接計算出左右字數的下標。（數組中下標為 i 的節點，左子節點下標為 i?2 ，右子節點下標為 i?2+1，父節點的下標為 i/2? 。）
如果我們把新插入的元素放到堆的最後，妳可以看我畫的這個圖，是不是不符合堆的特性了？於是，我們就需要進行調整，讓其重新滿足堆的特性，這個過程我們起了壹個名字，就叫做 堆化（heapify） 。
堆化實際上有兩種，從下往上和從上往下。這裏我先講從下往上的堆化方法。
堆化非常簡單，就是順著節點所在的路徑，向上或者向下，對比，然後交換。
我們把最後壹個節點放到堆頂，然後利用同樣的父子節點對比方法。對於不滿足父子節點大小關系的，互換兩個節點，並且重復進行這個過程，直到父子節點之間滿足大小關系為止。這就是 從上往下的堆化方法 。
壹個包含 n 個節點的完全二叉樹，樹的高度不會超過 log2?n。堆化的過程是順著節點所在路徑比較交換的，所以堆化的時間復雜度跟樹的高度成正比，也就是 O(logn)。插入數據和刪除堆頂元素的主要邏輯就是堆化，所以，往堆中插入壹個元素和刪除堆頂元素的時間復雜度都是 O(logn)。
這裏我們借助於堆這種數據結構實現的排序算法，就叫做堆排序。這種排序方法的時間復雜度非常穩定，是 O(nlogn)，並且它還是原地排序算法。
從後往前處理數組，並且每個數據都是從上往下堆化。
因為葉子節點往下堆化只能自己跟自己比較，所以我們直接從最後壹個非葉子節點開始，依次堆化就行了。
建堆的時間復雜度就是 O(n)。 推導過程見 極客時間--數據結構與算法之美
建堆結束之後，數組中的數據已經是按照大頂堆的特性來組織的。數組中的第壹個元素就是堆頂，也就是最大的元素。我們把它跟最後壹個元素交換，那最大元素就放到了下標為 n 的位置。
這個過程有點類似上面講的“刪除堆頂元素”的操作，當堆頂元素移除之後，我們把下標為 n 的元素放到堆頂，然後再通過堆化的方法，將剩下的 n?1 個元素重新構建成堆。堆化完成之後，我們再取堆頂的元素，放到下標是 n?1 的位置，壹直重復這個過程，直到最後堆中只剩下標為 1 的壹個元素，排序工作就完成了。
整個堆排序的過程，都只需要極個別臨時存儲空間，所以堆排序是原地排序算法。堆排序包括建堆和排序兩個操作，建堆過程的時間復雜度是 O(n)，排序過程的時間復雜度是 O(nlogn)，所以，堆排序整體的時間復雜度是 O(nlogn)。
堆排序不是穩定的排序算法，因為在排序的過程，存在將堆的最後壹個節點跟堆頂節點互換的操作，所以就有可能改變值相同數據的原始相對順序。
堆這種數據結構幾個非常重要的應用：優先級隊列、求 Top K 和求中位數。
假設我們有 100 個小文件，每個文件的大小是 100MB，每個文件中存儲的都是有序的字符串。我們希望將這些 100 個小文件合並成壹個有序的大文件。這裏就會用到優先級隊列。
這裏就可以用到優先級隊列，也可以說是堆。我們將從小文件中取出來的字符串放入到小頂堆中，那堆頂的元素，也就是優先級隊列隊首的元素，就是最小的字符串。我們將這個字符串放入到大文件中，並將其從堆中刪除。然後再從小文件中取出下壹個字符串，放入到堆中。循環這個過程，就可以將 100 個小文件中的數據依次放入到大文件中。
我們可以用優先級隊列來解決。我們按照任務設定的執行時間，將這些任務存儲在優先級隊列中，隊列首部（也就是小頂堆的堆頂）存儲的是最先執行的任務。
如何在壹個包含 n 個數據的數組中，查找前 K 大數據呢？我們可以維護壹個大小為 K 的小頂堆，順序遍歷數組，從數組中取出數據與堆頂元素比較。如果比堆頂元素大，我們就把堆頂元素刪除，並且將這個元素插入到堆中；如果比堆頂元素小，則不做處理，繼續遍歷數組。這樣等數組中的數據都遍歷完之後，堆中的數據就是前 K 大數據了。
中位數，顧名思義，就是處在中間位置的那個數。
使用兩個堆：壹個大頂堆， 壹個小頂堆。 小頂堆中的數據都大於大頂堆中的數據。
如果新加入的數據小於等於大頂堆的堆頂元素，我們就將這個新數據插入到大頂堆；否則，我們就將這個新數據插入到小頂堆。
也就是說，如果有 n 個數據，n 是偶數，我們從小到大排序，那前 2n? 個數據存儲在大頂堆中，後 2n? 個數據存儲在小頂堆中。這樣，大頂堆中的堆頂元素就是我們要找的中位數。如果 n 是奇數，情況是類似的，大頂堆就存儲 2n?+1 個數據，小頂堆中就存儲 2n? 個數據。
極客時間--數據結構與算法之美--28 | 堆和堆排序：為什麽說堆排序沒有快速排序快？