【leetcode】堆习题

215.数组中的第K个最大元素
给定整数数组 nums 和整数 k，请返回数组中第 k 个最大的元素。
请注意，你需要找的是数组排序后的第 k 个最大的元素，而不是第 k 个不同的元素。
你必须设计并实现时间复杂度为 O(n) 的算法解决此问题。
示例 1:
输入: [3,2,1,5,6,4], k = 2
输出: 5
示例 2:
输入: [3,2,3,1,2,4,5,5,6], k = 4
输出: 4
提示：
1 <= k <= nums.length <= 105
-104 <= nums[i] <= 104

/**
 * @param {number[]} nums
 * @param {number} k
 * @return {number}
 */
var findKthLargest = function(nums, k) {
    let arr = new MinHeap()
    nums.forEach(item => {
        arr.insert(item)
        if (arr.size() > k) {
            arr.pop()
        }
    })
    return arr.peek()
};

class MinHeap {
    constructor() {
        this.heap = []
    }
    // 换位置
    swap(i1, i2) {
        let temp = this.heap[i1]
        this.heap[i1] = this.heap[i2]
        this.heap[i2] = temp
    }
    // 找到父节点
    getParentIndex(index) {
        return Math.floor((index - 1) / 2)
    }
    // 上（前）移操作
    up(index) {
        if (index === 0) return
        const parentIndex = this.getParentIndex(index)
        if (this.heap[parentIndex] > this.heap[index] ) {
            this.swap( parentIndex, index )
            this.up(parentIndex)
        }
    }
    // 找到左侧子节点
    getLeftIndex(index) {
        return index * 2 + 1
    }
    // 找到右侧子节点
    getRigthIndex(index) {
        return index * 2 + 2
    }
    // 下（后）移操作
    down(index) {
        const leftIndex = this.getLeftIndex(index)
        const rightIndex = this.getRigthIndex(index)
        if (this.heap[leftIndex] < this.heap[index]) {
            this.swap(leftIndex, index)
            this.down(leftIndex)
        }
        if (this.heap[rightIndex] < this.heap[index]) {
            this.swap(rightIndex, index)
            this.down(rightIndex)
        }
    }
    // 添加元素
    insert( value ) {
        this.heap.push(value)
        this.up( this.heap.length-1 )
    }
    // 删除堆顶
    pop() {
        this.heap[0] = this.heap.pop()
        this.down(0)
    }
    // 获取堆顶
    peek() {
        return this.heap[0]
    }
    // 获取堆长度
    size() {
        return this.heap.length
    }
}