最近在学习A*,写了一个二叉堆
function BinaryHeap(compare) {
this.content = [];
this.compare = compare;
}BinaryHeap.prototype = {
push: function(item) {
this.content.push(item);
var i = this.content.length - 1; this.bubbleUp(i);
},
pop: function() {
var c = this.content;
var c0 = c[0];
var last = c.pop(); var hole = this.sink(0);
if(this.content.length > 0) {
c[hole] = last;
this.bubbleUp(hole);
}
return c0;
},
size: function() {
return this.content.length;
},
sink: function(i) {
var _this = this;
var c = this.content; function move(from, to) {
c[to] = c[from];
}
function findChild(x) { // find the less child
var left = 2*x+1, right = left+1;
if(c[left] === undefined) return null;
if(c[right] === undefined) return left;
return _this.compare(c[left], c[right]) ? left : right;
}
var ci;// child index
while((ci = findChild(i)) !== null) {
move(ci, i);
i = ci;
}
return i;
},
bubbleUp: function(i) {
var p, pi, item, c = this.content;
var item;
function swap(j, k) {
var tmp = c[k]; c[k] = c[j]; c[j] = tmp;
}
while(i >= 0) {
item = c[i];
pi = Math.floor((i-1)/2); // parent index
p = c[pi]; // parent item
if(this.compare(item, p)) {
swap(i, pi);
i = pi;
} else {
break;
}
}
}
};// test
heap = new BinaryHeap(function(a, b) {
return a < b;
});
Ext.each([10, 3, 4, 8, 2, 9, 7, 1, 2, 6, 2, 5], heap.push, heap);// while (heap.size() > 0)
// console.info(heap.pop());碰到几个问题:
1. 上面的代码中,计算元素位置时候,我是从0开始的, 第一个元素位置0,第二个位置1.。。 但很多书上和例子上都是从1开始,这样有什么好处吗?我觉得从0开始更直观,毕竟程序员都习惯数组从0开始
2. 还有没漂亮一点的写法,总觉得pop函数中的那个if判断不好。
3. 二叉堆除了用于方便地获取最值,还有什么其他用途
4. 为什么叫二叉"堆",只是因为看起来像个堆吗,和堆栈有无关系?