学习一下小顶堆

概念入门

完全二叉树

一棵深度为k的有n个结点的二叉树，对树中的结点按从上至下、从左到右的顺序进行编号，如果编号为i（1≤i≤n）的结点与满二叉树中编号为i的结点在二叉树中的位置相同，则这棵二叉树称为完全二叉树

堆

堆是一棵完全二叉树，其存储结构一般用的是数组

小顶堆

小顶堆就是堆顶的元素是当前子树里最小的一个元素的堆，对任意非叶子节点 有 Key[i]<=key[2i+1]&&Key[i]<=key[2i+2];

操作

构造

构造一棵小顶堆 即在存储数组的末尾添加一个元素 然后判断其能否满足小顶堆的性质，不满足即 把他与父节点交换位置，重复此步骤直到找到正确的位置:

/*
react scheduler React v0.20.1
*/
function siftUp(heap,node){
    let nodeIndex = heap.length;
    heap[nodeIndex] = node;
    while(true){
        /*
         假设某个根节点为i 则其
         left 为 2i + 1
         right 2i + 2
        * left - 1 是 2i 
        * right - 1 是 2i + 1；
        * 然后再右移相当于除以2向下取整都能得到正确的
        * 父节点位置  至于这里为什么用无符号右移而没有用>> 这点尚未清楚
        */
        let parentNodeIndex = nodeIndex - 1 >>> 1
        let parentNode = heap[parentNodeIndex]
        if( 
            parentNode !== undefined 
                &&
            parentNode > node
        ){
            heap[parentNodeIndex] = node
            heap[nodeIndex] = parentNode
            nodeIndex = parentNodeIndex
        }else{
            return;
        }
    }
}

删除

对于堆的删除来说，是指删除堆顶的元素 同时取出最后一个元素 从堆顶开始 找到左右子节点 选择其中比较小并且小于他的元素 依次比较 交换位置，重复此步骤直到满足小顶堆的性质：

function siftDown(heap){

    let parentIndex = 0;
    let parentNode = heap[0];
    let lastNode = heap.pop();
    const L = heap.length;

    while( parentIndex < L ){

        let leftIndex = 2*parentIndex + 1;
        let rightIndex = leftIndex + 1;
        let left = heap[leftIndex];
        let right = heap[rightIndex]

        if( rightIndex < L ){//左右子节点都存在
            if( left < lastNode ){
                if( right < left){
                    heap[parentIndex] = right;
                    heap[rightIndex] = lastNode;
                    parentIndex = rightIndex;
                }else{
                    heap[parentIndex] = left;
                    heap[leftIndex] = lastNode;
                    parentIndex = leftIndex;
                }
            }else if( right < lastNode ){
                heap[parentIndex] = right;
                heap[rightIndex] = lastNode;
                parentIndex = rightIndex;
            }else{
                break;
            }
        }else if( leftIndex < L){//只有左子节点
            if( left < lastNode ){
                heap[parentIndex] = left;
                heap[leftIndex] = lastNode;
                parentIndex = leftIndex;
            }else{
                break;
            }
        }else{
            break;
        }
    }
    return parentNode;
}