2
\$\begingroup\$

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());
\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.