https://github.com/vnues/data-structure-algorithm/blob/master/215.%20%E6%95%B0%E7%BB%84%E4%B8%AD%E7%9A%84%E7%AC%ACK%E4%B8%AA%E6%9C%80%E5%A4%A7%E5%85%83%E7%B4%A0.js

    1. const num = [3,2,1,5,6,4] 
    2. const  k = 2
    4. console.log(findKthLargest(num,6))
    6. // 可以使用堆排序来解决这个问题——建立一个大顶堆，做k−1 次删除操作后，堆顶元素就是我们要找的答案
    7. // ! 因为大顶堆的 最大数的肯定是在顶 如果我们再删除k-1次数 然后再调整大顶堆
    8. // 建堆的好处就是可以操作K次就拿到结果 而不是全部排序后再去拿到结果
    9. // 尤其要搞懂「建堆」、「调整」和「删除」的过程
    10. function findKthLargest(nums,  k) {
    11.     let heapSize = nums.length;
    12.     buildMaxHeap(nums, heapSize); // 构建大顶堆
    13.     // ! 删除k-1操作 就是相当于下沉 nums.length - k + 1次
    14.     // 比如k是nums.length 第k大  数组6个元素排序 5个排好就行 所以i>=0
    15.     for (let i = nums.length - 1; i >= nums.length - k + 1; --i) {
    16.         swap(nums, 0, i); // 进行下沉 也就是交换 大顶堆 大的放后面
    17.         --heapSize; 
    18.         maxHeapify(nums, 0, heapSize);
    19.     }
    20.     // !要找的目标值不进行下沉就行 在堆顶获取到
    21.     console.log(nums)
    22.     return nums[0]; // nums ===> [ 5, 3, 4, 1, 2, 6 ]
    23. }
    25.  // ! 自下而上构建大顶堆 ===>从最后一个非叶子节点构建再到根节点
    26.  // 非叶子节点
    27. function buildMaxHeap(a,  heapSize) {
    28.     // heapSize / 2 表示有多少个非叶子节点
    29.     for (let i = Math.floor(heapSize / 2)-1; i >= 0; --i) {
    30.         maxHeapify(a, i, heapSize);
    31.     } 
    32. }
    34. // ! 自上而下的「调整」
    35. function maxHeapify(a,  i,  heapSize) {
    36.      // 左子节点和右子节点
    37.      let l = i * 2 + 1, r = i * 2 + 2, largest = i;
    38.     if (l < heapSize && a[l] > a[largest]) {
    39.         largest = l;
    40.     } 
    41.     if (r < heapSize && a[r] > a[largest]) {
    42.         largest = r;
    43.     }
    44.     if (largest != i) {
    45.         swap(a, i, largest);
    46.         maxHeapify(a, largest, heapSize);
    47.     }
    48. }
    51. function swap(a,  i,  j) {
    52.     let temp = a[i];
    53.     a[i] = a[j];
    54.     a[j] = temp;
    55. }
    58. // 堆排序的步骤
    59. // 1.构造初始堆 给定无序序列结构 如下：注意这里的操作用数组
    60. // 2.此时从最后一个非叶子节点开始调整，从左到右，从上到下进行调整 ===> let i = Math.floor(heapSize / 2)-1
    61. // 3.将堆顶元素与末尾元素进行交换 ===>进行下沉操作