一、题目

给定整数数组 nums 和整数 k，请返回数组中第 k 个最大的元素。

请注意，你需要找的是数组排序后的第 k 个最大的元素，而不是第 k 个不同的元素。

二、示例

输入: [3,2,1,5,6,4] 和 k = 2
输出: 5

输入: [3,2,3,1,2,4,5,5,6] 和 k = 4
输出: 4

三、思路
本题采用最小堆的思想，使用数组遍历每一个元素，然后将其插入到最小堆中，然后维持一个最小堆的大小。当数组遍历完后，此时返回堆顶的元素。
四、代码

/**
 * @param {number[]} nums
 * @param {number} k
 * @return {number}
 */
class MinHeap {
  constructor() {
    this.heap = []
  }
  getParentIndex(index) {
     return Math.floor((index - 1) / 2)
  }
  shiftUp(index) {
    if (index < 1) return
    let parentIndex = this.getParentIndex(index)
    if (this.heap[parentIndex] > this.heap[index]) {
      this.swap(parentIndex, index)
      this.shiftUp(parentIndex)
    }
  }
  swap(index1, index2) {
    [this.heap[index1], this.heap[index2]] = [this.heap[index2], this.heap[index1]]
  }
  insert(value) {
    this.heap.push(value)
    this.shiftUp(this.heap.length - 1)
  }
  pop() {
    this.heap[0] = this.heap[this.heap.length - 1]
    this.heap.pop()
    this.shiftDown(0)
  }
  shiftDown(index) {
    let leftChildIndex = this.getLeftChildIndex(index)
    let rightChildIndex = this.getRightChildIndex(index)
    if (this.heap[leftChildIndex] < this.heap[index]) {
      this.swap(leftChildIndex, index)
      this.shiftDown(leftChildIndex)
    }
    if (this.heap[rightChildIndex] < this.heap[index]) {
      this.swap(rightChildIndex, index)
      this.shiftDown(rightChildIndex)
    }
  }
  getLeftChildIndex(index) {
    return index * 2 + 1
  }
  getRightChildIndex(index) {
    return index * 2 + 2
  }
  getSize() {
    return this.heap.length
  }
  getTopOne(){
    return this.heap[0]
  }
}
var findKthLargest = function(nums, k) {
    let newHeap = new MinHeap()
    for(let item of nums) {
        newHeap.insert(item)
        if(newHeap.getSize() > k) {
            newHeap.pop()
        }
    }
    return newHeap.getTopOne()
};

五、总结