Last active
May 2, 2022 03:09
-
-
Save cwli24/5cd2566dcd0ff04f6fbdaee968dc5ec5 to your computer and use it in GitHub Desktop.
Generic min heap class for JS (which lacks that DS built-in)
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
class MinHeap { | |
constructor(selector = x => x[0]) { | |
this.items = [0]; | |
this.selector = selector; | |
} | |
insert(item) { | |
let childIdx = this.items.length; | |
this.items.push(item); | |
let childItem = item; | |
let parentIdx = Math.trunc(childIdx/2), parentItem = this.items[parentIdx]; | |
while (childIdx > 1 && this.selector(parentItem) > this.selector(childItem)) { | |
[this.items[childIdx], this.items[parentIdx]] = [parentItem, childItem]; | |
childIdx = parentIdx; | |
childItem = this.items[childIdx]; | |
parentIdx = Math.trunc(childIdx/2); | |
parentItem = this.items[parentIdx]; | |
} | |
} | |
remove() { | |
let initialLen = this.items.length - 1; | |
if (initialLen == 1) | |
return this.items.pop(); | |
else if (initialLen <= 0) | |
return undefined; | |
const itemToReturn = this.items[1]; | |
this.items[1] = this.items.pop(); | |
let parentIdx = 1; | |
let leftChildIdx; | |
// Remember that heaps are complete trees--left is assigned before right | |
while ((leftChildIdx = parentIdx*2) < initialLen) { | |
let rightChildIdx = leftChildIdx + 1; | |
let smallerChildIdx; | |
if (rightChildIdx >= initialLen) { | |
smallerChildIdx = leftChildIdx; | |
} else { | |
smallerChildIdx = this.selector(this.items[leftChildIdx]) < this.selector(this.items[rightChildIdx]) ? | |
leftChildIdx : rightChildIdx; | |
} | |
let parentItem = this.items[parentIdx]; | |
let smallerChildItem = this.items[smallerChildIdx]; | |
if (this.selector(parentItem) > this.selector(smallerChildItem)) { | |
[this.items[smallerChildIdx], this.items[parentIdx]] = [parentItem, smallerChildItem]; | |
parentIdx = smallerChildIdx; | |
} else { | |
break; | |
} | |
} | |
return itemToReturn; | |
} | |
isEmpty() { | |
return this.items.length <= 1; | |
} | |
size() { | |
return this.items.length-1; | |
} | |
peek() { | |
if (this.items.length <= 1) | |
return undefined; | |
return this.items[1]; | |
} | |
} |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment