LoginSignup
10
8

More than 3 years have passed since last update.

@330k(k 330)

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

Last updated at Posted at 2017-09-13

概要

昔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ライセンス。

10
8
4

Register as a new user and use Qiita more conveniently

  1. You get articles that match your needs
  2. You can efficiently read back useful information
  3. You can use dark theme
What you can do with signing up
Sign upLogin
10
8