javascript实现优先级队列(小顶堆)
了解优先级队列的详细叙述请访问(java实现):java用数组实现优先级队列（小顶堆）
实验目的:
先按key优先，如果key值相等再按value.hg优先。
插入数据案例
q.insert({key:1,value:{hg:6}});
q.insert({key:1,value:{hg:4}});
q.insert({key:1,value:{hg:9}});
q.insert({key:2,value:{hg:1}});
q.insert({key:1,value:{hg:6}});
q.insert({key:2,value:{hg:4}});
q.insert({key:1,value:{hg:9}});
q.insert({key:1,value:{hg:1}});
实验结果
代码案例
<!DOCTYPE html>
<html>
<head>
<meta charset="utf-8">
<title>优先级队列测试</title>
</head>
<body>
优先级队列测试
</body>
<script>
var q = new Object();
q.queue=new Array();
q.n=0;
/**
* @param {Object} data
* 插入数据
*/
q.insert=function( data) {
this.queue[++this.n] = data;
this.swim(this.n);
return true;
}
/**
* 获取队列数据
*/
q.getDate=function() {
if(this.n==0){
return null;
}
var data = this.queue[1];
this.exchange(1, this.n);
this.n--;
this.sink(1);
this.queue[this.n+1]=0;
return data;
}
/**
* @param {Object} k
* 上浮操作
*/
q.swim=function( k) {
while (k > 1 && this.compare(k>>1, k)) {
this.exchange(k, k>>1);
k = k>>1;
}
}
/**
* @param {Object} i
* @param {Object} j
* 比较
*/
q.compare=function( i, j) {
if(this.queue[i].key>this.queue[j].key){
return true;
}else if(this.queue[i].key==this.queue[j].key){
if(this.queue[i].value.hg>this.queue[j].value.hg){
return true;
}else{
return false;
}
}else{
return false;
}
}
/**
* @param {Object} i
* @param {Object} j
* 交换
*/
q.exchange=function( i, j) {
var k=this.queue[i];
this.queue[i]=this.queue[j];
this.queue[j]=k;
}
/**
* @param {Object} k
* 下沉操作
*/
q.sink=function( k) {
while (k<<1 <= this.n) {
var j = k<<1;
if (j < this.n && this.compare(j, j+1))
j++;
if (!this.compare(k, j))
break;
this.exchange(k, j);
k = j;
}
}
q.insert({key:1,value:{hg:6}});
q.insert({key:1,value:{hg:4}});
q.insert({key:1,value:{hg:9}});
q.insert({key:2,value:{hg:1}});
q.insert({key:1,value:{hg:6}});
q.insert({key:2,value:{hg:4}});
q.insert({key:1,value:{hg:9}});
q.insert({key:1,value:{hg:1}});
var d;
console.log(q)
d=q.getDate();
console.log("数据----------- "+d.key+":"+d.value.hg);
d=q.getDate();
console.log("数据----------- "+d.key+":"+d.value.hg);
d=q.getDate();
console.log("数据----------- "+d.key+":"+d.value.hg);
d=q.getDate();
console.log("数据----------- "+d.key+":"+d.value.hg);
d=q.getDate();
console.log("数据----------- "+d.key+":"+d.value.hg);
d=q.getDate();
console.log("数据----------- "+d.key+":"+d.value.hg);
d=q.getDate();
console.log("数据----------- "+d.key+":"+d.value.hg);
d=q.getDate();
console.log("数据----------- "+d.key+":"+d.value.hg);
</script>
</html>
fixed
没有一个冬天不可逾越，没有一个春天不会来临。最慢的步伐不是跬步，而是徘徊，最快的脚步不是冲刺，而是坚持。