Cの場合は以下のようにして、二分ヒープを使用することができるらしい。
#include "BinaryHeap.h"
■実装
しかし、JavaScriptには二分ヒープのようなデータ構造が存在しないので、以下のように自力で実装する。
/** * BinaryHeap */ var BinaryHeap = function(){ var self = this; self._ary = []; } BinaryHeap.prototype._build = function(){ var self = this; /** * heapify * 3要素を比較し最も小さい要素を親とする * @param {array} ary * @param {int} i * @param {max} max */ var heapify = function(ary, i, max){ /** * swap * @param {array} ary * @param {int} x * @param {int} y */ var swap = function(ary, x, y){ var a = ary[x]; var b = ary[y]; ary[x] = b; ary[y] = a; return true; } var l = 2 * i + 1; var r = 2 * i + 2; var li = 0; if(l < max && ary[l].priority < ary[i].priority){ li = l; } else{ li = i; } if(r < max && ary[r].priority < ary[li].priority){ li = r; } if(li !== i){ swap(ary, i, li); heapify(ary, li, max); } } var ary = self._ary; for(var i = ary.length - 1; i >= 0; i--){ heapify(ary, i, self._ary.length); } } /** * BinaryHeap::insert * 要素をヒープに追加する * @param {Object} elm * @param {int} priority */ BinaryHeap.prototype.insert = function(elm, priority){ var self = this; self._ary.push({ "priority" : priority, "elm" : elm }); self._build(); } /** * BinaryHeap::changePriority * 要素の優先度を変更する * @param {Object} elm * @param {int} priority */ BinaryHeap.prototype.changePriority = function(elm, priority){ var self = this; var ary = self._ary; for(var i = 0; i < ary.length; i++){ if(elm === ary[i]["elm"]){ ary[i]["priority"] = priority; self._build(); return true; } } return false; } /** * BinaryHeap::getPrior * 優先度の高い要素を取得する */ BinaryHeap.prototype.getPrior = function(){ var self = this; var elm = self._ary.shift(); self._build(); return elm["elm"]; } /** * BinaryHeap::getList * ヒープを返す */ BinaryHeap.prototype.getList = function(){ var self = this; return self._ary; } // test code var pq = new BinaryHeap(); pq.insert('pochi', 0); pq.insert('son', 4); pq.insert('mike', 10); pq.insert('father', 1); pq.insert('mother', 2); console.log(pq.getList());
優先度つきキューに使用したいので、ヒープソートのコードを変更し最小ヒープとした。使用方法は以下のとおりである。
二分ヒープの生成
var pq = new BinaryHeap();
要素の追加
pq.insert(elm, priority);
優先度の変更
pq.changePriority(elm, priority);
最優先要素の取得
var elm = pq.getPrior();