Binary heap (priority queue) implementation in JavaScript

Question

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)
}

})()

Answer 1

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])