1
\$\begingroup\$

I wrote this heap implementation because I need it to run Dijkstra's algorithm to find paths in a game (for which reason I'd like this implementation not to be unreasonably slow...)

Sadly I don't know JavaScript well, much worse than C or C++ for sure, so I might've made some silly mistakes, I'd love You to point them out for me :)

For example, I'm unsure if keeping heap nodes in an array is an OK approach here; sadly I can't find the relevant SO post now, but I remember reading on SO that using arrays as memory pools results in a gross performance degradation in JavaScript. Keeping nodes in an array is pretty convinient for implementing a heap, but should I have refrained from this anyway?

Also I am aware that people usually tell me my coding style is horrible and unreadable, so I suppose I'm going to get similar comments here, how exactly did I fail this time?

The code seems correct though, it passes this test: https://paste.ee/p/edrYt which was generated with this C++ code: https://ideone.com/zpCtIz

Ah and I tried to stick to JSv5, I tried to refreain from using ES6 features. I hope none slipped through.

var GZKM = GZKM || {}

;(function() {

GZKM.Heap = function() {
    this.arr = []
}

GZKM.Heap.prototype._parentIndex = function(i) {
    return Math.floor((i+1)/2)-1
}

GZKM.Heap.prototype._leftChildIndex = function(i) {
    return 2*(i+1)-1
}

GZKM.Heap.prototype._rightChildIndex = function(i) {
    return 2*(i+1)
}

GZKM.Heap.prototype._swapNodes = function(node1, node2) {
    // Idea taken from this SO answer: https://stackoverflow.com/a/22053474/4385532
    // Doing it this way b/c this SO answer scared me that the standard way may lead to a memory leak: https://stackoverflow.com/a/872433/4385532
    this.arr[node1._i] = [this.arr[node2._i], this.arr[node2._i]=this.arr[node1._i]][0]
    node1._i = [node2._i, node2._i=node1._i][0]
}

GZKM.Heap.prototype._moveUp = function(node) {
    var canMove = function() {
        return node._i > 0
    }
    var mustMove = function() {
        return this.arr[this._parentIndex(node._i)].priority > node.priority
    }.bind(this)
    while(canMove() && mustMove())
        this._swapNodes(node, this.arr[this._parentIndex(node._i)])
}

GZKM.Heap.prototype._moveDown = function(node) {
    var canMove = function() {
        return this._leftChildIndex(node._i) < this.arr.length
    }.bind(this)    
    var nextNode = function() {
        if(this._rightChildIndex(node._i) >= this.arr.length ||
                this.arr[this._rightChildIndex(node._i)].priority > this.arr[this._leftChildIndex(node._i)].priority)
            return this.arr[this._leftChildIndex(node._i)]
        else return this.arr[this._rightChildIndex(node._i)]
    }.bind(this)
    var mustMove = function() {
        return nextNode().priority < node.priority
    }
    while(canMove() && mustMove())
        this._swapNodes(node, nextNode())
}

GZKM.Heap.prototype.push = function(priority, elt) {
    var eltIndex = this.arr.length;
    this.arr.push({elt: elt, priority: priority, _i: eltIndex})
    var ret = this.arr[eltIndex]
    this._moveUp(this.arr[eltIndex])
    return ret
}

GZKM.Heap.prototype.pop = function() {
    if(!this.arr.length) return undefined
    this._swapNodes(this.arr[0], this.arr[this.arr.length-1])
    var ret = this.arr.pop()
    this._moveDown(this.arr[0])
    return ret
}

GZKM.Heap.prototype.reprioritize = function(node, newPriority) {
    node.priority = newPriority
    this._moveUp(node)
    this._moveDown(node)
}

})()
\$\endgroup\$
1
\$\begingroup\$

Big f...reakin' bug:

GZKM.Heap.prototype.pop = function() {
    if(!this.arr.length) return undefined
    this._swapNodes(this.arr[0], this.arr[this.arr.length-1])
    var ret = this.arr.pop()
    this._moveDown(this.arr[0])
    return ret
}

After this.arr.pop() the array may very well be empty, and _moveDown is not prepared to being called with undefined, so we will get an exception here. I really thought the tests would cover this...well, they didn't.

Fixing this seems simple though:

if(this.arr.length)
    this._moveDown(this.arr[0])
\$\endgroup\$

Your Answer

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

Not the answer you're looking for? Browse other questions tagged or ask your own question.