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>