JavaScriptでPriorityQueue

優先度付きキューを実装する必要に駆られたので書きました。

実装

TypeScript

class PriorityQueue<T> {
    private container: T[] = [];
    private size = 0;
    private comp: (a: T, b: T) => boolean;
    constructor(comp = (a: T, b: T) => a < b) {
        this.comp = comp;
    }
    push(val: T) {
        let index = this.size;
        this.container[this.size] = val;
        ++this.size;

        for (let parent = 0|(index-1)/2;
             parent >= 0 && this.comp(this.container[parent], this.container[index]);
             index = parent, parent = 0|(index-1)/2) {
                 const tmp = this.container[index];
                 this.container[index] = this.container[parent];
                 this.container[parent] = tmp;
             }
    }
    pop() {
        this.container[0] = this.container[this.size-1];
        this.container.pop();
        --this.size;

        for (let index = 0, l = 1, r = 2;
             l < this.size && (this.comp(this.container[index], this.container[l]) || this.comp(this.container[index], this.container[r]));
             l = index * 2 + 1, r = index * 2 + 2) {
                 let target = l;

                 if (this.comp(this.container[index], this.container[r])) target = r;
                 if (this.comp(this.container[index], this.container[l]) && this.comp(this.container[index], this.container[r]))
                     if (this.comp(this.container[r], this.container[l])) target = l;
                 else target = r;

                 const tmp = this.container[index];
                 this.container[index] = this.container[target];
                 this.container[target] = tmp;
                 index = target;
             }
    }
    top() { return this.container[0]; }
    empty() { return this.size == 0; }
}

JavaScript

class PriorityQueue {
    constructor(comp = (a, b) => a < b) {
        this.size = 0;
        this.container = [];
        this.comp = comp;
    }
    push(val) {
        let index = this.size;
        this.container[this.size] = val;
        ++this.size;

        for (let parent = 0|(index-1)/2;
            parent >= 0 && this.comp(this.container[parent], this.container[index]);
            index = parent, parent = 0|(index-1)/2) {
            const tmp = this.container[index];
            this.container[index] = this.container[parent];
            this.container[parent] = tmp;
        }
    }
    pop() {
        this.container[0] = this.container[this.size-1];
        this.container.pop();
        --this.size;

        for (let index = 0, l = 1, r = 2;
            l < this.size && (this.comp(this.container[index], this.container[l]) || this.comp(this.container[index], this.container[r]));
            l = index * 2 + 1, r = index * 2 + 2) {
            let target = l;

            if (this.comp(this.container[index], this.container[r])) target = r;
            if (this.comp(this.container[index], this.container[l]) && this.comp(this.container[index], this.container[r]))
            if (this.comp(this.container[r], this.container[l])) target = l;
            else target = r;

            const tmp = this.container[index];
            this.container[index] = this.container[target];
            this.container[target] = tmp;
            index = target;
        }
    }
    top() { return this.container[0]; }
    empty() { return this.size == 0; }
}

使い方

new PriorityQueue()でインスタンスを生成できます。デフォルトは降順で要素が出てきます。

const q = new PriorityQueue<number>();
for (const e of [4, 1, 6, 2, 5, 3, 9, 10, 8, 7]) {
    q.push(e);
}
while (!q.empty()) {
    console.log(q.top());
    q.pop();
}

比較関数を渡すことで優先順を変えることができます。

const q = new PriorityQueue<number>((a:number, b:number) => a>b); // 昇順
for (const e of [4, 1, 6, 2, 5, 3, 9, 10, 8, 7]) {
    q.push(e);
}
while (!q.empty()) {
    console.log(q.top());
    q.pop();
}