javascript实现优先级队列(小顶堆)

weblog 1133 0 0

了解优先级队列的详细叙述请访问(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>

 

猜你喜欢
数据结构与算法 2720 ,largestout)的行为特征。通常采用数据结构来是不同于的另一种。每次从中取出的是具有最高权的元素。操作:1.往中添加数据2.从中获取数据
official 183 《操作系统》时间片轮转算法思想:公平地、轮流地为各个进程服务,让每个进程在一定时间间隔内都可以得到响应算法规则:按照各进程到达就绪的顺序,轮流让各个进程执行一个时间片(如100ms)。若进程未在
数据结构与算法 8053 问题描述思路:典型的广度搜索算法,根据字典序大,可以确定遍历的循序,因为字典序DLRU,所以对于每一个节点往下走,然后向左走,然后向右走,然后向上走。则最后首到达出口的一条路径就是符合
数据结构与算法 497 ) 跳跃表(知道原理,应用,最后自己一遍) 并查集(建议结合刷题学习) 栈与 栈(必学) (必学) (必学) 多反馈(原理与应用) 哈希表(必学)
数据结构与算法 835 上一篇:广度搜索算法(bfs、广搜)java-数据结构和算法用邻接矩阵表示图的定点之间的关系如下图数据结构则用邻接矩阵表示为: privatestaticintmap
official 20 上一篇《(mq)rabbitmq安装延时插件延时消息1》文章中介绍了rabbitmq安装延时插件。本编将继续结合代码来延时(基于springboot项目)。下方所有源代码均已上传
数据结构与算法 421 ,放入后台的一个执行中,后台可以慢慢执行,当中没有业务数据时,使该执行线程进入等待状态。当业务数据添加进中后唤醒处于等待状态的执行线程,继续处理业务。一、阻塞packagecom.
java基础 621 基于双向链表结构直接代码:packagethreadTest.test6;publicclassNodeE{ privateEe; privateNodeEprve; privateNodeEnext; publicNode(Ee){ super(); this.e=e; } publicEgetE(){ returne; } publicvoidsetE(Ee){ this.e=e; }
目录