JavaScriptによる優先度付きキューの実装

概要

昔JavaScriptで実装した各種アルゴリズムによる優先度付きキュー。
いずれも最大ヒープなので、優先度が高い順に取り出される。

昔書いたJavaScriptなので、今どきのコーティングスタイルではないかも。

共通

共通のメソッドは下記の4つ。

• enqueue(priority, data) : キューに優先度priority(数値)のdataを追加。
• dequeue() : キューから最も優先度の高いdataを取り出して、キューから削除。
• top() : 最も優先度の高いdataを取り出す。削除はしない。
• size() : 要素数を返す。

var queue = new binary_heap();             // newはあってもなくても可
//var queue = new d_ary_heap(4);           // d-aryのdは指定可能(省略時は4)
//var queue = new pairing_heap();
//var queue = new leftist_heap();
//var queue = new skew_heap();
//var queue = new fibonacci_heap();

queue.enqueue(3, "data1");                 // enqueue(優先度, データ)で追加
queue.enqueue(1, "data2");
queue.enqueue(2, "data3");
console.log(queue.dequeue());  // data1    // 優先度最大のデータを返す(削除する)
console.log(queue.top());      // data3    // 優先度最大のデータを返す(削除しない)
console.log(queue.dequeue());  // data3
console.log(queue.dequeue());  // data2

2分ヒープ(Binary Heap)

構造が単純でそこそこ高速。

binary_heap.js

function binary_heap(){
	"use strict";
	var _data = [];
	var _size = 0;
	var enqueue = function(priority, value){
		var data = _data;
		var i = 0;
		var p = 0;
		var ret = null;
		
		if(_size){
			data.push({p: priority, v: value});
			i = _size;
			p = (i - 1) >> 1;//Math.floor((i - 1) * 0.5);	// parent
			while(p >= 0){
				if(data[p].p < data[i].p){
					ret = data[i];
					data[i] = data[p];
					data[p] = ret;
				
					i = p;
					p = (i - 1) >> 1;//Math.floor((i - 1) * 0.5);
				}else{
					break;
				}
			}
		}else{
			data.push({p: priority, v: value});
		}
		_size = _size + 1;
	};
	var dequeue = function(){
		var data = _data;
		var size = _size - 1;
		var result = null;
		var i = 0;
		var c1 = 1;	// left child
		var c2 = 2;	// right child
		var p0 = 0.0;
		var p1 = 0.0;
		var p2 = 0.0;
		var ret = null;
		
		if(_size){
			result = data[0].v;
			data[0] = data[size];
			data.pop();
			
			while(c1 < size){
				if(c2 < size){
					p0 = data[i].p;
					p1 = data[c1].p;
					p2 = data[c2].p;
				
					if((p1 < p2) && (p0 < p2)){
						ret = data[i];
						data[i] = data[c2];
						data[c2] = ret;
						i = c2;
					}else if(p0 < p1){
						ret = data[i];
						data[i] = data[c1];
						data[c1] = ret;
						i = c1;
					}else{
						break;
					}
					c1 = (i << 1) + 1;
					c2 = (i << 1) + 2;
				}else{
					p0 = data[i].p;
					p1 = data[c1].p;
					
					if(p0 < p1){
						ret = data[i];
						data[i] = data[c1];
						data[c1] = ret;
					}
					break;
				}
			}
			
			_size = size;
			return result;
		}else{
			return (void 0);
		}
	};
	var top = function(){
		return _data[0].v;
	};
	var size = function(){
		return _size;
	};
	
	return {
		name: 'Binary Heap',
		enqueue: enqueue,
		dequeue: dequeue,
		top: top,
		size: size
	};
}

d-aryヒープ (d-ary Heap)

2分ヒープの一般化版。d = 2のときは2分ヒープ。d = 4のとき性能が良いと言われる。
FirefoxはChromeに比べ配列の処理が得意なのか、特に高速。

d_ary_heap.js

function d_ary_heap(d){
	"use strict";
	var _d = d || 4;
	var _data = [];
	var _size = 0;
	var _dinv = 1 / _d;
	var enqueue = function(priority, value){
		var data = _data;
		var ret = null;
		var i = 0;
		var p = 0;
		
		if(_size){
			data.push({p: priority, v: value});
			i = _size;
			p = ~~((i - 1) * _dinv);
			while(p >= 0){
				if(data[p].p < data[i].p){
					ret = data[i];
					data[i] = data[p];
					data[p] = ret;
				
					i = p;
					p = ~~((i - 1) * _dinv);
				}else{
					break;
				}
			}
		}else{
			data.push({p: priority, v: value});
		}
		_size = _size + 1;
	};
	var dequeue = function(){
		var data = _data;
		var size = _size - 1;
		var result = null;
		var i = 0;
		var c = 1;
		var p0 = 0.0;
		var pmax = 0.0;
		var pret = 0.0;
		var cmax = 0;
		var j = 0;
		var jmax = 0;
		var ret = null;
		
		if(_size){
			result = data[0].v;
			data[0] = data[size];
			data.pop();
			
			while(c < size){
				p0 = data[i].p;
				pmax = data[c].p;
				cmax = c;
				
				jmax = c + _d;
				if(jmax > size){
					jmax = size;
				}
				for(j = c + 1; j < jmax; j++){
					pret = data[j].p;
					if(pmax < pret){
						pmax = pret;
						cmax = j;
					}
				}
				if(p0 < pmax){
					ret = data[i];
					data[i] = data[cmax];
					data[cmax] = ret;
				}else{
					break;
				}
				i = cmax;
				c = i * _d + 1;
			}
			
			_size = size;
			return result;
		}else{
			return (void 0);
		}
	};
	var top = function(){
		return _data[0].v;
	};
	var size = function(){
		return _size;
	};
	
	return {
		name: 'd-ary Heap (d=' + _d + ')',
		enqueue: enqueue,
		dequeue: dequeue,
		top: top,
		size: size
	};
}

ペアリングヒープ(Pairing Heap)

Chromeだと一番高速になることが多い。データによらず速度が安定している。
配列を使わない実装ではシンプル。

pairing_heap.js

function pairing_heap(){
	"use strict";
	var _root = null;
	var _size = 0;
	var _merge = function (i, j){
		var ret = null;

		if(i === null) return j;
		if(j === null) return i;
		
		if(i.p < j.p){
			ret = i;
			i = j;
			j = ret;
		}
		j.next = i.head;
		i.head = j;
		
		return i;
	};
	var _mergeList = function (s){
		var n = null;
		var a = null;
		var b = null;
		var j = null;
		
		while(s !== null){
			a = s;
			b = null;
			s = s.next;
			a.next = null;
			if(s !== null){
				b = s;
				s = s.next;
				b.next = null;
			}
			a = _merge(a, b);
			a.next = n;
			n = a;
		}
		while(n !== null){
			j = n;
			n = n.next;
			s = _merge(j, s);
		}
		return s;
	};
	
	var enqueue = function(priority, value){
		_root = _merge(_root, {
			p: priority,
			v: value,
			next: null,
			head: null
		});
		_size = _size + 1;
	};
	var dequeue = function(){
		var result = null;

		if(_size){
			result = _root.v;
			_root = _mergeList(_root.head);
			_size = _size - 1;
		
			return result;
		}else{
			return (void 0);
		}
	};
	var top = function(){
		return _root.v;
	};
	var size = function(){
		return _size;
	};
	
	return {
		name: 'Pairing Heap',
		enqueue: enqueue,
		dequeue: dequeue,
		top: top,
		size: size
	};
}

Leftist Heap

場合によってはPairing Heapよりも高速なこともある。

leftist_heap.js

function leftist_heap(){
	"use strict";
	var _root = null;
	var _size = 0;
	var _merge = function(i, j){
		var ret = null;
		
		if(i === null) return j;
		if(j === null) return i;
		
		if(i.p < j.p){
			ret = i;
			i = j;
			j = ret;
		}
		i.right = _merge(i.right, j);
		if((i.left === null) || (i.left.s < i.right.s)){
			ret = i.right;
			i.right = i.left;
			i.left = ret;
		}
		i.s = ((i.right === null) ? 0 : i.right.s) + 1;
		
		return i;
	};
	var enqueue = function(priority, value){
		_root = _merge(_root, {
			p: priority,
			v: value,
			left: null,
			right: null,
			s: 1
		});
		_size = _size + 1;
	};
	var dequeue = function(){
		var result = null;
		
		if(_size){
			result = _root.v;
			_root = _merge(_root.left, _root.right);
			_size = _size - 1;
			
			return result;
		}else{
			return (void 0);
		}
	};
	var top = function(){
		return _root.v;
	};
	var size = function(){
		return _size;
	};
	
	return {
		name: 'Leftist Heap',
		enqueue: enqueue,
		dequeue: dequeue,
		top: top,
		size: size
	};
}

Skew Heap

Leftist Heapよりも少し単純な実装だが少し遅め。

skew_heap.js

function skew_heap(){
	"use strict";
	var _root = null;
	var _size = 0;
	var _merge = function(i, j){
		var ret = null;

		if(i === null) return j;
		if(j === null) return i;
		
		if(i.p < j.p){
			ret = i;
			i = j;
			j = ret;
		}
		i.right = _merge(i.right, j);
		ret = i.right;
		i.right = i.left;
		i.left = ret;
		
		return i;
	};
	var enqueue = function(priority, value){
		_root = _merge(_root, {
			p: priority,
			v: value,
			left: null,
			right: null
		});
		_size = _size + 1;
	};
	var dequeue = function(){
		var result = null;
		
		if(_size){
			result = _root.v;
			_root = _merge(_root.left, _root.right);
			_size = _size - 1;
			
			return result;
		}else{
			return (void 0);
		}
	};
	var top = function(){
		return _root.v;
	};
	var size = function(){
		return _size;
	};
	
	return {
		name: 'Skew Heap',
		enqueue: enqueue,
		dequeue: dequeue,
		top: top,
		size: size
	};
}

フィボナッチヒープ(Fibonacci Heap)

今いち理解できない。他のヒープに比べて遅い(2〜3倍時間がかかる)。
もっと速くできるかも。

fibonacci_heap.js

function fibonacci_heap(){
	"use strict";
	var _top = null;
	var _size = 0;
	var _mergeList = function(i, j){
		var ret = null;

		if(i === null) return j;
		if(j === null) return i;
		
		ret = i.next;
		i.next = j.next;
		i.next.prev = i;
		j.next = ret;
		j.next.prev = j;

		return i.p > j.p ? i : j;
	};
	
	var enqueue = function(priority, value){
		var newnode = {
			p: priority,
			v: value,
			marked: false,
			rank: 0,
			next: null,
			prev: null,
			firstchild: null
		};
		newnode.next = newnode;
		newnode.prev = newnode;
		
		_top = _mergeList(_top, newnode);
		_size = _size + 1;
	};
	var dequeue = function(){
		var top = _top;
		var result = top;
		var ranks = [];
		var roots = [];
		var i = 0;
		var l = 0;
		var curr = null;
		var other = null;
		var min = null;
		var max = null;

		if(_size){
			_size = _size - 1;
			
			if(top.next === top){
				top = null;
			}else{
				top.prev.next = top.next;
				top.next.prev = top.prev;
				top = top.next;
			}
			
			top = _mergeList(top, result.firstchild);
			
			if(top === null){
				_top = top;
				return result.v;
			}

			curr = top;
			do{
				roots.push(curr);
				curr = curr.next;
			} while(curr !== top);
			
			for(i = 0, l = roots.length; i < l; i++){
				curr = roots[i];
				while(true){
					if(ranks[curr.rank] === undefined){
						ranks[curr.rank] = curr;
						break;
					}
					other = ranks[curr.rank];
					ranks[curr.rank] = undefined;
					
					if(curr.p < other.p){
						min = curr;
						max = other;
					}else{
						min = other;
						max = curr;
					}
					
					min.next.prev = min.prev;
					min.prev.next = min.next;
					
					min.next = min.prev = min;
					max.firstchild = _mergeList(max.firstchild, min);
					
					min.marked = false;
					max.rank = max.rank + 1;
					
					curr = max;
				}
				if(curr.p > top.p){
					top = curr;
				}

			}
			
			_top = top;
			return result.v;
		}else{
			return (void 0);
		}
	};
	var top = function(){
		return _top.v;
	};
	var size = function(){
		return _size;
	};
	
	return {
		name: 'Fibonacci Heap',
		enqueue: enqueue,
		dequeue: dequeue,
		top: top,
		size: size
	};
}

ライセンス

いずれもMITライセンス。

• もともと英語だけで公開していたGitHub: https://github.com/330k/priorityqueue_js
• ベンチマーク: https://330k.github.io/priorityqueue_js/benchmark.html