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

weblog 精帖
274

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

 

猜你喜欢
  • blog 生成树Kruskal算法-数据结构和算法

    生成树算法和其应用         什么是最生成树:一个有 n 个结点的连通图的生成树是原图的极连通子图,且包含原图中的所有 n 个结点,并且有保持图连通的最少的边。最生成树可以用krus
  • blog jvm内存模型分析(5)内存溢出以及分析

    jvm内存模型分析(5)内存溢出以及分析1.模拟内存溢出代码package test;import java.util.ArrayList;import java.util.List;/** * VM Args:-Xms20m -Xmx
  • blog java工具 jmap 命令的使用方法以及内存快照的创建及分析(1)

            jmap是java虚拟机自带的一种内存映像工具,我们可以通过该工具配合不同的参数来查看java虚拟机内存的详细信息(如程序中出的所有对象的数量以及占用内存大等),以及通过虚拟机内存
  • blog 递归合并两递增链表-合并后保持递增序

    递归合并两递增链表-合并后保持递增序java描述数据结构:单链表算法:递归链表节点package club.test;/*** * 链表节点 * @author jiajia * */public class Node { publi
  • blog 链式的基本操作 c++

    链式的基本操作 c++class node{public : int data; node * next; node * prev;};#include "node.h"class queue{private :
  • blog js javascript对象数组的浅拷贝和深拷贝

    概念 浅拷贝         只会拷贝一层,如果数组中是对象,则只会拷贝对象引用,如果是基本数据类型则会拷贝值。  深拷贝         多
  • blog javascript js滑动定位(锚点定位)

    1.锚点定位很简单两行搞定:<a href='#anchorName'>点击跳转到anchorName的位置</a><a name='anchorName'>anchorName</a>2.js代码,并带滑动效果 $(document)
  • blog 递归全排算法 c++描述

    递归全排算法 c++描述#includeusing namespace std;//交换void exchange(int *a,int i,int j){ if(i==j){ return ;
  • blog 阻塞及其原理

    1.什么是阻塞 阻塞是一个在基础上又支持了两个附加操作的。2.支持阻塞的插入方法:满时,会阻塞插入元素的线程,直到不满。1.支持阻塞的移除方法:空时,获取元素的线程会等待变为非空。2.阻塞
  • blog 什么是单调栈?

    对于栈,一般来讲是进后出。而所谓 单调栈 则是在栈的 进后出 基础之上额外添加一个特性:从栈到栈底的元素是严格递增(or递减)。那么具体的进栈过程如下:1.对于单调递增栈,若当前进栈元素为 e,从栈开始遍历元素,把于 e 或者等于