创建大顶堆找topK

顺序存储二叉树特性：

第 n 个元素的 左子节点 为 2*n+1
第 n 个元素的 右子节点 为 2*n+2
第 n 个元素的 父节点 为 (n-1)/2
最后一个非叶子节点为 Math.floor(arr.length/2)-1

大顶堆特性：每个节点的值都 大于或等于 其左右孩子节点的值

arr[i] >= arr[2*i+1] && arr[i] >= arr[2*i+2], //i 对应第几个节点，i 从 0 开始编号

小顶堆特性：每个节点的值都 小于或等于 其左右孩子节点的值

arr[i] <= arr[2*i+1] && arr[i] <= arr[2*i+2], //i 对应第几个节点，i 从 0 开始

 解题思路：

1.将待排序序列构造成一个大顶堆

注意：这里使用的是数组，而不是一颗二叉树

2.此时：整个序列的 最大值就是堆顶的根节点

3.将其 与末尾元素进行交换，此时末尾就是最大值

4.然后将剩余 n-1 个元素重新构造成一个堆，这样 就会得到 n 个元素的次小值。如此反复，便能的得到一个有序序列。

/**
 * @param {number[]} nums
 * @param {number} k
 * @return {number}
 */
 // 整个流程就是上浮下沉【上浮就是构建成大顶堆，下浮就是将最大值浮到末尾】
var findKthLargest = function(nums, k) {
  let heapSize=nums.length
  buildMaxHeap(nums,heapSize) // 构建好了一个大顶堆
  // 进行下沉 大顶堆是最大元素下沉到末尾【因为是找topK,所以下沉到第nums.length-k+1即可】
  for(let i=nums.length-1;i>=nums.length-k+1;i--){
      swap(nums,0,i) // 交换堆顶元素和末尾元素，
      --heapSize // 下沉后的元素不参与到大顶堆的调整
      // 重新调整大顶堆
        maxHeapify(nums, 0, heapSize);
  }
  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){
      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) // 进行节点调整
          // 继续调整下面的非叶子节点
          maxHeapify(nums,largest,heapSize)
      }
  }
  function swap(a,  i,  j){
      let temp = a[i];
      a[i] = a[j];
      a[j] = temp;
  }
};
let arr = [4,6,8,5,9]
console.log(findKthLargest(arr,2)) //8

 参考地址：力扣