94 lines
2.6 KiB
TypeScript
94 lines
2.6 KiB
TypeScript
/**
|
|
* 二叉堆
|
|
* @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;
|
|
}
|
|
}
|
|
}
|
|
} |