mlheap.d2l

转载其他网站的资料与大家分享

//##################################################
//######     Matts Binary Heap Library      ########
//##################################################

/*
----------------------------------------------------
Version 1.0.0
----------------------------------------------------
Copyright (C) 2003 Matt Lanteigne aka mattlant <[e-mail]>
----------------------------------------------------

This program is free software; you can redistribute it and/or modify
it under the terms of the GNU General Public License as published by the
Free Software Foundation; either version 2, or (at your option) any later
version.

This program is distributed in the hope that it will be useful, but
WITHOUT ANY WARRANTY; without even the implied warranty of MERCHANTIBILITY
or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU General Public License
for more details.

----------------------------------------------------
SCRIPT USAGE:

to create a heap, first instantiate it. When instantiating, make sure to provide
the name of the variable on your object that holds the priority. You can optionally
specify which order the heap will be in. If nothing is provide, a default priority
name of "p" will be used and a highest value has highest priority system.

var myheap = new oHeap("priority", mlHEAPHIGH);

to add an object sinply use the insert method and provide the actual object:

myheap.Insert(object);

to get the first item AND remove it use teh remove method:

var highestitem = myheap.Remove();

to get the first item AND NOT remove it use the peek method:

var highestitem = myheap.Peek();

to get the heaps length use the getLength method:

var lengthofheap = myheap.getLength();
*/


const mlHEAPLOW = 1; //lower number has higher priority
const mlHEAPHIGH = 2; //higher number has higher priority


function oHeap(pr, o)
{
	if(!pr) {pr = "p";}
	if(!o) {o = mlHEAPHIGH;}
	this._p = pr; //private
	this._o = o; //private
	if(this._o == mlHEAPHIGH){
		this.Insert = oHeap_inserthigh;
		this.Remove = oHeap_removehigh; }
	else{
		this.Insert = oHeap_insertlow;
		this.Remove = oHeap_removelow; }

	this.Peek = oHeap_peek;
	this.getLength = oHeap_qlength;

	this._heap = new Array(); //private
	this._heap[0] = null;

	function oHeap_inserthigh(d)
	{
		var i = this._heap.length;
		this._heap[this._heap.length] = null;
		while (i > 1 && this._heap[i >> 1][this._p] < d[this._p])
		{
			this._heap[i] = this._heap[i >> 1];
			i >>= 1;
		}
		this._heap[i] = d;
	}
	function oHeap_removehigh()
	{
		if (this._heap.length == 1) return null;
		var i = 1;
		var j;
		var d = this._heap[1];
		var tmp = this._heap[this._heap.length-1];
		while (i <= ((this._heap.length-1) >> 1)) {
			j = i << 1;
			if ((j < this._heap.length-1) && this._heap[j][this._p] < this._heap[j + 1][this._p]) {
				j++;
			}
			if (this._heap[j][this._p] <= tmp[this._p]) {
				break;
			}
			this._heap[i] = this._heap[j];
			i = j;
		}
		this._heap[i] = tmp;
		this._heap.length--;
		return d;
	}
	function oHeap_insertlow(d)
	{
		var i = this._heap.length;
		this._heap[this._heap.length] = null;
		while (i > 1 && this._heap[i >> 1][this._p] > d[this._p])
		{
			this._heap[i] = this._heap[i >> 1];
			i  >>= 1;
		}
		this._heap[i] = d;
	}
	function oHeap_removelow()
	{
		if (this._heap.length == 1) return null;
		var i = 1;
		var j;
		var d = this._heap[1];
		var tmp = this._heap[this._heap.length-1];
		while (i <= ((this._heap.length-1) >> 1)) {
			j = i << 1;
			if ((j < this._heap.length-1) && this._heap[j][this._p] > this._heap[j + 1][this._p]) {
				j++;
			}
			if (this._heap[j][this._p] >= tmp[this._p]) {
				break;
			}
			this._heap[i] = this._heap[j];
			i = j;
		}
		this._heap[i] = tmp;
		this._heap.length--;
		return d;
	}

	function oHeap_peek()
	{
		if (this._heap.length == 1) return null;
		return this._heap[1];
	}

	function oHeap_qlength()
	{
		return this._heap.length;
	}

}