/**
* 二叉堆
 * @author BrightLi
 * @since 2020/4/18
 */

export default class BinaryHeap
{
    private _content:any[];
    private _scoreFunction:(node:any)=>number;
// 構造函數
    public constructor(scoreFunction:(node:any)=>number){
        this._content=[];
        this._scoreFunction=scoreFunction;
    }
// 是否為空
    public get isEmpty():boolean{
        return this._content.length<1;
    }
// 是否包含節點
    public contain(node:any){
        var pos=this._content.indexOf(node);
        return pos != -1;
    }
// 壓入節點
    public push(node:any){
        this._content.push(node);
        this.siftDown(this._content.length-1);
    }
// 彈出節點，一定是最小值
    public pop():any{
        var result=this._content[0];
        var end=this._content.pop();
        if(this._content.length>0){
            this._content[0]=end;
            this.siftDown(0);
        }
        return result;
    }
// 更新節點
    public update(node:any){
        var n=this._content.indexOf(node);
        if(n==-1){
            return;
        }
        this.siftDown(n);
        this.siftUp(n);
    }

    private siftDown(n:number){
        var element=this._content[n];
        while(n>0){
            var parentNode=((n+1)>>1)-1,
            parent=this._content[parentNode];
            if(this._scoreFunction(element)<this._scoreFunction(parent)){
                this._content[parentNode]=element;
                this._content[n]=parent;
                n=parentNode;
            }else{
                break;
            }
        }
    }

    private siftUp(n:number) {
        var length = this._content.length,
        element = this._content[n],
        elementScore = this._scoreFunction(element);
        while(true) {
            var child2N = (n + 1) << 1, child1N = child2N - 1;
            var swap = null;
            if (child1N < length) {
                var child1 = this._content[child1N],
                child1Score = this._scoreFunction(child1);
                if (child1Score < elementScore){
                    swap = child1N;
                }
            }
            if (child2N < length) {
                var child2 = this._content[child2N],
                child2Score = this._scoreFunction(child2);
                if (child2Score < (swap === null ? elementScore : child1Score))
                    swap = child2N;
            }
            if (swap !== null) {
                this._content[n] = this._content[swap];
                this._content[swap] = element;
                n = swap;
            }else {
                break;
            }
        }
    }
}