LeetCode——數組中的第K個最大元素（堆排序-大頂堆）

這是我參與8月更文挑戰的第8天，活動詳情檢視： 8月更文挑戰

題目描述

解題思路

本題如果直接再用API解題肯定是不行的，因為面試不可能考你API如何使用，前幾天寫過這個題目是通過快速排序寫的，這次我們采用堆排序，通過大頂堆的方式來求出第K個最大的元素，其實這類問題都屬于經典的TOP K問題，屬于面試的常考題。

1. 建構大頂堆

為什麼要建構大頂堆，是因為大頂堆的對頂元素是整個數組中最大的元素.我們正式利用這點來求解問題的。

1. 建構大頂堆的第一步是從最後一個非葉子節點開始，一直周遊到根節點.
2. 一個節點的左子節點是 2*n + 1.
3. 一個節點的右子節點是 2*n + 2.
4. 一個節點的父節點是(n-1) / 2 (向下取整)
5. 一棵樹的最後一個非葉子節點是 Math.flool(nums.length/2)-1.

2. 将大頂堆下沉K-1次，得到的就是第K大的元素

假如，我們要求的是第一大的元素，K-1就是零，也就是說不需要進行下沉，此時的大頂堆的堆頂就是最大的元素。若K-1=2，隻需下沉兩次，堆頂就是我們的最大的元素。所謂的下沉就是将堆頂與末尾元素進行交換。然後将堆的長度減一之後繼續進行堆化。

解題代碼

// 通過大頂堆求解問題
var findKthLargest = function(nums, k) {
    // 堆的大小
    let heapSize = nums.length;
    // 調用大頂堆函數
    buildMaxHeap(nums,heapSize);
    // 要想求第K大的元素，就需要将大頂堆下沉K-1次，每下沉一次進行一次重新的堆化；
    for (let i = 0; i < k - 1; i++ ) {
        swap(nums,0,nums.length - 1 - i);
        // 将最後一個元素忽略，不參與堆化
        nums
        heapSize--;
        // 從第0個元素開始繼續進行堆化
        maxHeapify(nums,0,heapSize);
    }
    // 此時堆頂就是第K個最大元素
    return nums[0]
    // 建構大頂堆
    function buildMaxHeap(nums,heapSize) {
        for (let i = Math.floor(heapSize / 2) - 1; i >= 0; i--) {
            maxHeapify(nums,i,heapSize)
        }
    }
    function maxHeapify(nums,i,heapSize) {
        // 首先假定第i個是最大的
        let max = i;
        let leftChild = 2 * i + 1;
        let rightChild = 2 * i + 2;
        // 如果下标不越界（即子孩子存在），并且子節點小于第i個元素
        if (leftChild < heapSize && nums[leftChild] > nums[max]) {
            max = leftChild;
        }
        if (rightChild < heapSize && nums[rightChild] > nums[max]) {
            max = rightChild;
        }
        // 判斷是否發生了交換
        if (max !== i) {
            swap(nums,i,max);
            // 交換之後，從下面上來的元素的位置後面需要繼續進行堆化
            maxHeapify(nums,max,heapSize);
        }
    }
    function swap (nums,i,j) {
        let temp = nums[i];
        nums[i] = nums[j];
        nums[j] = temp;
    }
};
findKthLargest([8,5,0,3,7,1,2], 3)
複制代碼      

題目反思

• 學會使用大頂堆的方式來求解TOP K問題。
• 本題的思路也是解決堆排序的核心思路。