题解 | #最小的K个数#

代码量有点大，但是清晰的堆排序

function GetLeastNumbers_Solution(input, k)
{
    // write code here
    let ans = [];
    if(!input.length || k>input.length){return ans;}
    let heap = new MaxHeap(); 
    for(let i = 0;i<input.length;i++){
        if(i<k){
            heap.insert(input[i]);
        }else{
            if(input[i]<heap.peek()){
            let q = heap.delete();
            heap.insert(input[i]);
        }
        }
        
    }
    while(k--){
        ans.push(heap.delete());
    }
    return ans;
}
class MaxHeap{
    constructor(){
        this.heap = []
    }
    parentNode(index){return index-1 >> 1;}
    leftNode(index){ return index * 2 +1;}
    rightNode(index){ return index * 2 +2;}
    shiftUp(index){
        if(index == 0){return;}
        let parentnode = this.parentNode(index);
        if(this.heap[index]>this.heap[parentnode]){
            [this.heap[index],this.heap[parentnode]] = [this.heap[parentnode],this.heap[index]];
            this.shiftUp(parentnode);
        }
    }
    shiftDown(index){
        if(index == this.heap.length-1){return;}
        let leftnode = this.leftNode(index);
        let rightnode = this.rightNode(index);
        if(this.heap[index]<this.heap[leftnode]){
            [this.heap[index],this.heap[leftnode]] = [this.heap[leftnode],this.heap[index]];
            this.shiftDown(leftnode);
        }
        if(this.heap[index]<this.heap[rightnode]){
            [this.heap[index],this.heap[rightnode]] = [this.heap[rightnode],this.heap[index]];
            this.shiftDown(rightnode);
        }
    }
    insert(value){
        this.heap.push(value);
        this.shiftUp(this.heap.length-1);
    }
    delete(){
        if(this.heap.length == 1) return this.heap.pop();
        let tmp = this.heap[0];
        this.heap[0] = this.heap.pop();
        this.shiftDown(0)
        return tmp;
    }
    peek(){
        return this.heap[0];
    }
}
module.exports = {
    GetLeastNumbers_Solution : GetLeastNumbers_Solution
};