二叉堆是一种特殊的堆，二叉堆是完全二元树（二叉树）或者是近似完全二元树（二叉树）。
二叉堆实用数组来表示，存贮节点的，其规则如图（1）
（1）
二叉堆是完全根据完全二叉树的规则来向数组里放置元素的
其首个元素 0 他的左右分支 分别对应这数组里的 元素 1 和元素 2 元素的左右分支 对应着 元素 3 和元素 4 也就是说 1 比0 小 2 比1 大 （对应着二叉树的左右分支），因为和完全二叉树非常相似所以我们能得出 和完全二叉树 相同的规律 0的左分支对应着他的 2*n+1 = 1 右分支为 2*n+2 = 2;由这个条件 我们可以对 二叉堆 进行 插入节点 以及 遍历二叉堆；
用js写一个二叉堆对象：
function Heap(){
this.heapBody = [];
this.end = 0; //设置一个尾指针 用来遍历值
this.add = function(value){
n = 0;
do{
pointValue = this.heapBody[n];//用来表示这个值
if(typeof(pointValue)!=undefined&&pointValue!=null){//如果定义了且不是null 那么证明有值 再往下找
if(value<pointVlaue){//如果要添加的值 小于这个值的本身 就去找 2n+1 也就是完全二叉树中的 左节点
n = 2*n+1;
}else{//大于 就去找 2n+2 也就是二叉树中的 右子节点
n = 2*n+2;
}
}else{//如果遍历到的值 为未定义 或者 null 那么证明他已经没有子节点了
for(;this.end<n;this.end++){//先用尾指针遍历一边 把未定义的 都插入null 防止乱了完全二叉树的规则
this.headBody[this.end] = null;
}
this.headBody[n] = value; //最后把值 给最后一位节点 并且退出循环
break;
}
}while(true);
}
this.iterater = function(){//二叉堆遍历
var thisa = this; // 把this的值 放进一个变量中 防止this跳转
var rsArr = [];//创建一个数组 用来存放 遍历出来的值
function sort(n){//写一个排序方法
p = 2*n+1;
v = thisa.heapBody[p];
if(typeof(v)!='undefined'&&v=null){//递归 2*n+1 也就是左子树
sort(p);
}
rsArr.push(thisa.heapBody[n]);
p = 2*n+2;
v = thisa.heapBody[p];
if(typeof(v)!='undefined'&&v=null){//递归 2*n+2 也就是右子树
sort(p);
}
}
sort(0);//从下表为0的元素 开始递归 最会将把所有元素按照大小顺序 插入到数组中
return rsArr;//返回插入完成的数组；
}
}
网友评论