力扣215題， 給定整數(shù)數(shù)組nums和整數(shù)k，請(qǐng)返回?cái)?shù)組中第k個(gè)最大的元素。 請(qǐng)注意，你需要找的是數(shù)組排序后的第k個(gè)最大的元素，而不是第k個(gè)不同的元素。

分析：按照“找最大用小堆，找最小用大堆，找中間用兩個(gè)堆”，這道題用最小堆來(lái)解決，構(gòu)造一個(gè)大小只有K的最小堆。舉個(gè)例子，序列[2, 4, 1, 3, 2, 5, 3, 6, 6, 9],比如找第4大的數(shù)，先讓前四個(gè)入堆，之后繼續(xù)遍歷與堆頂元素進(jìn)行比較，比堆頂元素大才能入堆否則不行。

新元素的插入只是替換根元素，然后重新構(gòu)造最小堆，完成之后的根元素就是第4大的元素。

代碼如下：

function findKthLargest(nums, k) {let heapSize = nums.length;buildMaxHeap(nums, heapSize); // 構(gòu)建好一個(gè)大頂堆// 進(jìn)行下沉，大頂堆是最大元素下沉到末尾for (let i = nums.length - 1; i >= nums.length - k + 1; i--) {swap(nums, 0, i);// 下沉后的元素不參與到大頂堆的調(diào)整--heapSize;// 重新調(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 left = i*2 + 1;let right = i*2 + 2;let largest = i;if (left < heapSize && nums[left] > nums[largest]) {largest = left;}if (right < heapSize && nums[right] > nums[largest]) {largest = right;}if (largest !== i) {// 進(jìn)行節(jié)點(diǎn)調(diào)整swap(nums, i, largest); // 繼續(xù)調(diào)整下面的非葉子節(jié)點(diǎn)maxHeapify(nums, largest, heapSize);}}function swap(arr, i, j) {let temp = a[i];a[i] = a[j];a[j] = temp;}}

參考：落落落洛克