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