解題思路

?
堆排序整個流程可以總結(jié)為：上浮下沉
?

為什么解決本題需要用到堆？

?
很多同學(xué)可能會想到這樣一種解決，我把數(shù)組全部排序好，這樣就可以拿到第k大的元素，這樣是一種解法，但是我們是需要第K大的元素，不一定要全部排序好再去拿，只針對部分元素進(jìn)行排序，這樣的復(fù)雜度顯然可以降低的
?

也就是可以轉(zhuǎn)化為：「使用堆排序來解決這個問題——建立一個大頂堆，做k?1 次刪除操作后,堆頂元素就是我們要找的答案」（堆排序過程中，不全部下沉，下沉nums.length-k+1,然后堆頂可以拿到我們top k答案了）

堆排序

基本介紹

堆排序是利用 「堆」 這種 「數(shù)據(jù)結(jié)構(gòu)」 而設(shè)計的一種排序算法，它是一種選擇排序，最壞、最好、平均時間復(fù)雜度均為 O(nlogn)，它是不穩(wěn)定排序。

?
注意因為完全二叉樹的性質(zhì)，可以用數(shù)組表示對應(yīng)的樹結(jié)構(gòu)（所以，堆排序過程中，你是看不到樹這數(shù)據(jù)結(jié)構(gòu)的，用數(shù)組進(jìn)行映射了），這叫順序存儲
?

順序存儲二叉樹

特點(diǎn)

第 n 個元素的左子節(jié)點(diǎn) 為 「2*n+1」
第 n 個元素的右子節(jié)點(diǎn) 為 「2*n+2」
第 n 個元素的父節(jié)點(diǎn) 為 「(n-1)/2」
最后一個非葉子節(jié)點(diǎn)為 「Math.floor(arr.length/2)-1」

堆是具有以下性質(zhì)的完全二叉樹：

大頂堆：每個節(jié)點(diǎn)的值都 「大于或等于」 其左右孩子節(jié)點(diǎn)的值
注：「沒有要求左右值的大小關(guān)系」
小頂堆：每個節(jié)點(diǎn)的值都 「小于或等于」 其左右孩子節(jié)點(diǎn)的值

舉例說明：

大頂堆舉例

對堆中的節(jié)點(diǎn)按層進(jìn)行編號，映射到數(shù)組中如下圖

大頂堆特點(diǎn)：arr[i] >= arr[2*i+1] && arr[i] >= arr[2*i+2]，i 對應(yīng)第幾個節(jié)點(diǎn)，i 從 0 開始編號

小頂堆舉例

小頂堆特點(diǎn)：arr[i] <= arr[2*i+1] && arr[i] <= arr[2*i+2]，i 對應(yīng)第幾個節(jié)點(diǎn)，i 從 0 開始

排序說明

升序：一般采用大頂堆
降序：一般采用小頂堆

基本思想

將待排序序列構(gòu)造成一個大頂堆
注意：這里使用的是數(shù)組，而不是一顆二叉樹
此時：整個序列的 「最大值就是堆頂?shù)母?jié)點(diǎn)」
將其 「與末尾元素進(jìn)行交換」，此時末尾就是最大值
然后將剩余 n-1 個元素重新構(gòu)造成一個堆，這樣就會得到 n 個元素的次小值。如此反復(fù)，便能的得到一個有序序列。

堆排序步驟圖解

對數(shù)組 4,6,8,5,9 進(jìn)行堆排序，將數(shù)組升序排序。

步驟一：構(gòu)造初始堆

給定無序序列結(jié)構(gòu) 如下：注意這里的操作用數(shù)組，樹結(jié)構(gòu)只是參考理解

將給定無序序列構(gòu)造成一個大頂堆。

「此時從最后一個非葉子節(jié)點(diǎn)開始調(diào)整」，從左到右，從上到下進(jìn)行調(diào)整。

葉節(jié)點(diǎn)不用調(diào)整，第一個非葉子節(jié)點(diǎn) arr.length/2-1 = 5/2-1 = 1，也就是元素為 6 的節(jié)點(diǎn)。

比較時：先讓 5 與 9 比較，得到最大的那個，再和 6 比較，發(fā)現(xiàn) 9 大于 6，則調(diào)整他們的位置。

找到第二個非葉子節(jié)點(diǎn) 4，由于 [4,9,8] 中，9 元素最大，則 4 和 9 進(jìn)行交換

此時，交換導(dǎo)致了子根 [4,5,6] 結(jié)構(gòu)混亂，將其繼續(xù)調(diào)整。[4,5,6] 中 6 最大，將 4 與 6 進(jìn)行調(diào)整。

此時，就將一個無序序列構(gòu)造成了一個大頂堆。

步驟二：將堆頂元素與末尾元素進(jìn)行交換

將堆頂元素與末尾元素進(jìn)行交換，「使其末尾元素最大」。然后繼續(xù)調(diào)整，再將堆頂元素與末尾元素交換，得到第二大元素。如此反復(fù)進(jìn)行交換、重建、交換。

將堆頂元素 9 和末尾元素 4 進(jìn)行交換

重新調(diào)整結(jié)構(gòu)，使其繼續(xù)滿足堆定義

再將堆頂元素 8 與末尾元素 5 進(jìn)行交換，得到第二大元素 8

后續(xù)過程，繼續(xù)進(jìn)行調(diào)整、交換，如此反復(fù)進(jìn)行，最終使得整個序列有序

總結(jié)思路

將無序序列構(gòu)建成一個堆，根據(jù)升序降序需求選擇大頂堆
將堆頂元素與末尾元素交換，將最大元素「沉」到數(shù)組末端
重新調(diào)整結(jié)構(gòu)，使其滿足堆定義，然后繼續(xù)交換堆頂與當(dāng)前末尾元素，反復(fù)執(zhí)行調(diào)整、交換步驟，直到整個序列有序。

步驟

這里想說的幾點(diǎn)注意事項（代碼實現(xiàn)的關(guān)鍵思路）：

第一步構(gòu)建初始堆：「是自底向上構(gòu)建，從最后一個非葉子節(jié)點(diǎn)開始」。
第二步就是下沉操作讓尾部元素與堆頂元素交換，「最大值被放在數(shù)組末尾」，并且縮小數(shù)組的length，不參與后面大頂堆的調(diào)整
第三步就是調(diào)整：「是從上到下，從左到右」,因為堆頂元素下沉到末尾了，要重新調(diào)整這顆大頂堆

代碼模板

?
官方的代碼模板我參考了下，比一些書籍寫的都好記，所以可以參考作為堆排序的模板
?

/**
 * @param {number[]} nums
 * @param {number} k
 * @return {number}
 */
 // 整個流程就是上浮下沉
var findKthLargest = function(nums, k) {
   let heapSize=nums.length
    buildMaxHeap(nums,heapSize) // 構(gòu)建好了一個大頂堆
    // 進(jìn)行下沉 大頂堆是最大元素下沉到末尾
    for(let i=nums.length-1;i>=nums.length-k+1;i--){
        swap(nums,0,i)
        --heapSize // 下沉后的元素不參與到大頂堆的調(diào)整
        // 重新調(diào)整大頂堆
         maxHeapify(nums, 0, heapSize);
    }
    return nums[0]
   // 自下而上構(gòu)建一顆大頂堆
   function buildMaxHeap(nums,heapSize){
     for(let i=Math.floor(heapSize/2)-1;i>=0;i--){
        maxHeapify(nums,i,heapSize)
     }
   }
   // 從左向右，自上而下的調(diào)整節(jié)點(diǎn)
   function maxHeapify(nums,i,heapSize){
       let l=i*2+1
       let r=i*2+2
       let largest=i
       if(l < heapSize && nums[l] > nums[largest]){
           largest=l
       }
       if(r < heapSize && nums[r] > nums[largest]){
           largest=r
       }
       if(largest!==i){
           swap(nums,i,largest) // 進(jìn)行節(jié)點(diǎn)調(diào)整
           // 繼續(xù)調(diào)整下面的非葉子節(jié)點(diǎn)
           maxHeapify(nums,largest,heapSize)
       }
   }
   function swap(a,  i,  j){
        let temp = a[i];
        a[i] = a[j];
        a[j] = temp;
   }
};

進(jìn)行堆排序

findKthLargest(nums,nums.length)
// 或者調(diào)整一下 let i=nums.length-1;i>=nums.length-k+1;的條件就行

一文講懂堆排序，解決topK問題