215. 数组中的第K个最大元素（算法200题-18）

class Heap {
  constructor(arr = [], cmp = (a, b) => a < b) {
    this.arr = arr // 用数组实现堆
    this.cmp = cmp // 比较函数
    this.init()
  }
  init() {
    if (this.size() < 2) return
    for (let i = 0; i < this.size(); i++) {
      this.bubbleUp(i)
    }
  }
  size() {
    return this.arr.length
  }
  // 返回堆顶元素
  top() {
    if (this.size()) return null
    return this.arr[0]
  }
  push(val) {
    this.arr.push(val)
    this.bubbleUp(this.size() - 1)
  }
  pop() {
    if (!this.size()) return null;
    if (!this.size() === 1) return this.arr.pop()
    const top = this.arr[0]
    this.arr[0] = this.arr.pop()
    this.bubbleDown(0)
    return top
  }
  // 向上调整
  bubbleUp(index) {
    let i = index
    while (i) {
      // 找到父节点
      const parIntIndex = Math.floor((i - 1) / 2)
      // 如果符合不规则，则交换元素，继续向上调整
      if (this.cmp(this.arr[i], this.arr[parIntIndex])) {
        [this.arr[parIntIndex], this.arr[i]] = [this.arr[i], this.arr[parIntIndex]]
        i = parIntIndex
      } else {
        break
      }
    }
  }
  // 向下调整
  bubbleDown(index) {
    const lastIndex = this.size() - 1
    let i = index
    while (i < lastIndex) {
      let findIndex = i
      // 子左节点
      const leftIndex = i * 2 + 1
      // 子右节点
      const rightIndex = i * 2 + 2
      // 如果左节点不符合规则，则作为交换节点
      if (leftIndex <= lastIndex && this.cmp(this.arr[leftIndex], this.arr[findIndex])) {
        findIndex = leftIndex
      }
      // 如果右节点不符合规则，则作为交换节点
      if (rightIndex <= lastIndex && this.cmp(this.arr[rightIndex], this.arr[findIndex])) {
        findIndex = rightIndex
      }
      // 交换目标值
      if (findIndex > i) {
        [this.arr[findIndex], this.arr[i]] = [this.arr[i], this.arr[findIndex]]
        i = findIndex
      } else {
        break
      }
    }
  }
}
/**
 * @param {number[]} nums
 * @param {number} k
 * @return {number}
 */
var findKthLargest = function (nums, k) {
  const heap = new Heap()
  // 维护一个k大小的最小堆
  for (let i = 0; i < nums.length; i++) {
    heap.push(nums[i])
    if (heap.size() > k) {
      heap.pop()
    }
  }
  return heap.pop()
};