//最小二叉堆  https://eloquentjavascript.net/1st_edition/appendix2.html

export class BinaryHeap<T>{
    private _content: T[] = [];
    private _scoreFunc: (node: T) => number = null;

    constructor(func: (node: T) => number) {
        this._content = [];
        this._scoreFunc = func;
    }

    insert(element: T) {
        //将新元素添加到数组的末尾
        this._content.push(element);
        //让它冒泡
        this._bubbleUp(this._content.length - 1);
    }

    remove(element: T) {
        //要删除一个值,必须在数组中搜索它
        let length = this._content.length;
        for (let i = 0; i < length; ++i) {
            if (this._content[i] != element) continue;
            //找到后,重复pop中的过程,将洞填满。
            let end = this._content.pop();
            //如果弹出的元素是需要删除的元素,那么就完成了
            if (i == length - 1) break;
            this._content[i] = end;
            //否则我们将删除的元素替换为弹出的元素,并允许它根据情况向上或向下浮动
            this._bubbleUp(i);
            this._sinkDown(i);
            break;
        }
    }

    root() {
        //存储第一个元素,以便稍后返回
        let result = this._content[0];
        //获取数组末尾的元素
        let end = this._content.pop();
        //如果还剩下任何元素,将end元素放在开始位置,让它下沉
        if (this._content.length > 0) {
            this._content[0] = end;
            this._sinkDown(0);
        }
        return result;
    }

    size() {
        return this._content.length;
    }

    clear() {
        this._content = [];
    }

    print() {
        console.log(this._content);
    }

    private _sinkDown(idx: number) {
        //查找目标元素及其得分
        let length = this._content.length;
        let element = this._content[idx];
        let elemScore = this._scoreFunc(element);
        while (true) {
            //计算子元素的索引
            let child2N = (idx + 1) * 2;
            let child1N = child2N - 1;
            //这用于存储元素的新位置(如果有的话)
            let swap: number = null;
            //如果第一个子元素存在(在数组中)
            let child1Score = 0;
            if (child1N < length) {
                //查找并计算它的分数
                let child1 = this._content[child1N];
                child1Score = this._scoreFunc(child1);
                //如果分数小于元素的分数,则需要进行交换
                if (child1Score < elemScore) swap = child1N;
            }
            //对另一个子级做同样的检查
            if (child2N < length) {
                let child2 = this._content[child2N];
                let child2Score = this._scoreFunc(child2);
                if (child2Score < (swap == null ? elemScore : child1Score)) swap = child2N;
            }
            //不需要进一步交换,我们完成了
            if (!swap) break;
            //否则,交换并继续
            this._content[idx] = this._content[swap];
            this._content[swap] = element;
            idx = swap;
        }
    }

    private _bubbleUp(idx: number) {
        //获取必须移动的元素
        let element = this._content[idx], score = this._scoreFunc(element);
        //当值为0时,元素不能再向上移动了
        while (idx > 0) {
            //计算父元素的索引,并获取它
            let parentN = Math.floor((idx + 1) / 2) - 1, parent = this._content[parentN];
            //如果父级的分数较低,事情就会有条不紊,我们也就完事了
            if (score >= this._scoreFunc(parent)) break;
            //否则,将父元素与当前元素交换并继续
            this._content[parentN] = element;
            this._content[idx] = parent;
            idx = parentN;
        }
    }
}

// class PathNode {
//     id: number = 0;
//     count: number = 0;
//     constructor(id: number, count: number) {
//         this.id = id;
//         this.count = count;
//     }
// }

// let tree = new BinaryHeap<PathNode>((node: PathNode) => { return node.count; });

// let node = new PathNode(5,24);
// tree.insert(new PathNode(1,8));
// tree.insert(new PathNode(2,37));
// tree.insert(new PathNode(3,65));
// tree.insert(new PathNode(4,54));
// tree.insert(node);
// tree.insert(new PathNode(6,23));
// tree.insert(new PathNode(7,30));
// tree.insert(new PathNode(8,2));

// tree.print();

// node.count = 1;
// tree.remove(node);

// tree.insert(node);

// tree.print();