堆

堆

特殊的完全二叉树

所有节点大于等于它的子节点

JS中常用数组表示堆

- 左侧子节点：2*index+1;

- 右侧子节点：2*index+2

- 父节点：(index-1)/2

用处：快速找出最大值最小值；找出第K个最大最小元素；

// #### 堆
// 特殊的完全二叉树
// 所有节点大于等于它的子节点JS中常用数组表示堆

// - 左侧子节点：2*index+1;
// - 右侧子节点：2*index+2
// - 父节点：(index-1)/2

// 用处：快速找出最大值最小值；找出第K个最大最小元素；

class Minheap{
    constructor(){
        this.heap = [];
    }
    swap(i1, i2){
        const temp = this.heap[i1];
        this.heap[i1] = this.heap[i2]
    }
    //获取父节点
    getParentIndex(i){
        // return Math.floor((i-1)/2)
        return (i-1) >> 1;
    }
    getLeftIndex(i){
        return i * 2 + 1;
    }
    getRightIndex(i){
        return i * 2 + 2;
    }
    //交换
    swap(i1,i2){
        const temp = this.heap[i1];
        this.heap[i1] = this.heap[i2];
        this.heap[i2] = temp;
    }
    //上移
    shiftUp(index){
        const parentIndex = this.getParentIndex(index);
        if(this.heap[parentIndex]> this.heap[index]){
            this.swap(parentIndex,index);
            this.shiftUp(parentIndex);
        }
    }
    //下移
    shiftDown(index){
        const leftIndex = this.getLeftIndex(index);
        const rightIndex = this.getRightIndex(index);
        if(this.heap[leftIndex]