I would appreciate any feedback on syntax, naming convention, possible shortcuts, clarity of code and any other constructive feedback. This code was based off of the Priority Queue chapter in The Algorithm Design Manual.

CODE

'use strict';

function getRandomInt(min, max) {
  return Math.floor(Math.random() * (max - min)) + min;
}

class PriorityQueue {
    constructor(values) {
        this._n = -1;
        this._Q = [];

        if (Array.isArray(values)) {
            for (let value of values) {
                this.insert(value);
            }
        }
    }

    get n() {
        return this._n;
    }

    set n(value) {
        this._n = value;
        return;
    }

    get Q() {
        return this._Q;
    }

    set Q(value) {
        this._Q = value;
        return;
    }

    getParent(n) {
        if (n === 0) return -1;
        return Math.floor((n - 1) / 2);
    }

    getYoungChild(n) {
        return (n + 1) * 2 - 1;
    }

    insert(x) {
        this.Q[++this.n] = x;
        this.bubbleUp(this.n);
    }

    bubbleUp(x) {
        var parent = this.getParent(x);
        if (this.Q[parent] > this.Q[x]) {
            this.swap(parent, x);
            this.bubbleUp(parent);
        }
    }

    bubbleDown(parent) {
        var child = this.getYoungChild(parent);
        var min_index = parent;

        for (let i=0; i<=1; i++) {
            if (this.Q[min_index] > this.Q[child+i]) min_index = child+i;
        }

        if (min_index !== parent) { 
            this.swap(parent, min_index);
            this.bubbleDown(min_index);
        }
    }

    swap(x, y) {
        var temp = this.Q[x];
        this.Q[x] = this.Q[y];
        this.Q[y] = temp;
    }

    extractMin() {
        if (this.n < 1) throw 'The queue is empty.';

        var min = this.Q[0];

        if (this.n === 1) {
            this.Q = [];
            this.n = 0;
            return min;
        }

        if (this.n === 2) {
            this.Q = [this.Q[1]];
            this.n = 1;
            return min;
        }

        this.Q[0] = this.Q.splice(this.n, 1)[0];
        this.bubbleDown(0);
        this.n--;

        return min;
    }

    heapsort() {
        var original = this.Q;
        var A = [];

        for (let i=0; i<=this.n; i++) {
            A.push(this.extractMin());
        }
        this.Q = original;
        return A;
    }
}

var test = [];
for (let i=0; i<20; i++) {
    test.push(getRandomInt(0, 999));
}

console.log('test array is', test);

var pq = new PriorityQueue(test);

console.log(pq.heapsort());
share|improve this question

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Browse other questions tagged or ask your own question.