topk 问题用堆解决

    1. /**
    2.  * @param {number[]} nums
    3.  * @param {number} k
    4.  * @return {number}
    5.  */
    6.  // 整个流程就是上浮下沉
    7. var findKthLargest = function(nums, k) {
    8.    let heapSize=nums.length
    9.     buildMaxHeap(nums,heapSize) // 构建好了一个大顶堆
    10.     // 进行下沉 大顶堆是最大元素下沉到末尾
    11.     for(let i=nums.length-1;i>=nums.length-k+1;i--){
    12.         swap(nums,0,i)
    13.         --heapSize // 下沉后的元素不参与到大顶堆的调整
    14.         // 重新调整大顶堆
    15.          maxHeapify(nums, 0, heapSize);
    16.     }
    17.     return nums[0]
    18.    // 自下而上构建一颗大顶堆
    19.    function buildMaxHeap(nums,heapSize){
    20.      for(let i=Math.floor(heapSize/2)-1;i>=0;i--){
    21.         maxHeapify(nums,i,heapSize)
    22.      }
    23.    }
    24.    // 从左向右，自上而下的调整节点
    25.    function maxHeapify(nums,i,heapSize){
    26.        let l=i*2+1
    27.        let r=i*2+2
    28.        let largest=i
    29.        if(l < heapSize && nums[l] > nums[largest]){
    30.            largest=l
    31.        }
    32.        if(r < heapSize && nums[r] > nums[largest]){
    33.            largest=r
    34.        }
    35.        if(largest!==i){
    36.            swap(nums,i,largest) // 进行节点调整
    37.            // 继续调整下面的非叶子节点
    38.            maxHeapify(nums,largest,heapSize)
    39.        }
    40.    }
    41.    function swap(a,  i,  j){
    42.         let temp = a[i];
    43.         a[i] = a[j];
    44.         a[j] = temp;
    45.    }
    46. };