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