day21-数组中的第k个最大元素

215. 数组中的第K个最大元素

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

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

示例 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

解法1:构建最小堆

/**
 * @param {number[]} nums
 * @param {number} k
 * @return {number}
 */
var findKthLargest = function(nums, k) {
    const minHeap = new MinHeap();
    for(let i=0;i<nums.length;i++){
        if(minHeap.heap.length < k){
            minHeap.insert(nums[i]);
        }else if(nums[i] > minHeap.heap[0]){
            minHeap.heap[0] = nums[i]
            minHeap.heapifyDown(0)
        }
    }
    return minHeap.heap[0]
};

class MinHeap{
    constructor() {
        this.heap = [];
    }
    // 获取父节点位置
    getParentIndex(index) {
        return Math.floor((index - 1)/2)
    }
    // 获取左侧子节点位置
    getLeftChildIndex(index) {
        return 2 * index + 1
    } 
    // 获取右侧子节点位置
    getRightChildIndex(index) {
        return 2 * index + 2
    }
    // 交换数组中的两个元素
    swap(i,j){
        // 交换数组中的两个元素
        [this.heap[i],this.heap[j]] = [this.heap[j],this.heap[i]]
    }
    // 从当前节点向上堆化
    heapifyUp(index){
        const parentIndex = this.getParentIndex(index)
        if(parentIndex >=0 && this.heap[index] < this.heap[parentIndex]){
            // 如果当前节点小于父节点，则交换它们，并继续向上堆化
            this.swap(index,parentIndex)
            this.heapifyUp(parentIndex)
        }
    }

    // 从当前节点向下堆化
    heapifyDown(index){
        const leftChildIndex = this.getLeftChildIndex(index)
        const rightChildIndex = this.getRightChildIndex(index)
        let smallestIndex = index;
        // 如果左子节点小于当前节点，则更新最小值的索引为左子节点的索引
        if(leftChildIndex<this.heap.length && this.heap[leftChildIndex] < this.heap[smallestIndex]){
            smallestIndex = leftChildIndex
        }

        // 如果右子节点小于当前节点（及可能更新后的最小值），则更新最小值的索引为右子节点
        if(rightChildIndex < this.heap.length && this.heap[rightChildIndex] < this.heap[smallestIndex]){
            smallestIndex = rightChildIndex
        }

        // 如果最小值的索引不是当前节点的索引，则交换它们，并继续向下堆化
        if (smallestIndex !== index) {
            this.swap(index, smallestIndex)
            this.heapifyDown(smallestIndex)
        }

    }

    // 插入元素到堆中
    insert(value) {
        this.heap.push(value)
        this.heapifyUp(this.heap.length - 1)
    }

    // 提取堆顶的最小值 
    extractMin() {
        if (this.heap.length === 0) {
            return null
        }
        const minValue = this.heap[0]
        this.heap[0] = this.heap.pop()
        this.heapifyDown(0)
        return minValue
    }
}