Skip to content

Instantly share code, notes, and snippets.

@thg303
Created April 30, 2019 06:54
  • Star 0 You must be signed in to star a gist
  • Fork 0 You must be signed in to fork a gist
Star You must be signed in to star a gist
Save thg303/66f5359a572ca3dd649e967db642ea20 to your computer and use it in GitHub Desktop.
class MinHeap {
constructor() {
this.data = [];
}
add (item) {
let newData = [...this.data, item];
// it's the first item in the heap
if (this.data.length === 0) {
return this.data = newData;
}
let itemIndex = this.data.length;
let parentIndex = this.getParentIndexFor(itemIndex);
while (parentIndex !== null && newData[parentIndex].priority > newData[itemIndex].priority) {
let temp = {...newData[parentIndex]};
newData[parentIndex] = {...newData[itemIndex]};
newData[itemIndex] = temp;
itemIndex = parentIndex;
parentIndex = this.getParentIndexFor(itemIndex)
}
return this.data = newData;
}
remove() {
let [output, ...rest] = this.data
this.data = [];
for (let i = 0; i < rest.length; i++) {
this.add(rest[i]);
}
return output;
}
isEmpty () {
return this.data.length === 0
}
getParentIndexFor(index) {
if (index === 0) {
return null;
}
let parentIndex = Math.floor((index + 1) / 2) - 1
return parentIndex
}
}
let heap = new MinHeap();
heap.add({value: 1, priority: 23});
heap.add({value: 2, priority: 21});
heap.add({value: 3, priority: 18});
heap.add({value: 4, priority: 5});
heap.add({value: 5, priority: 19});
heap.add({value: 6, priority: 13});
heap.add({value: 7, priority: 11});
heap.add({value: 8, priority: 3});
heap.add({value: 9, priority: 0});
// console.log(heap.data)
console.log('done...');
heap.add({value: 10, priority: 9});
console.log(heap.data.map(item => item.priority));
console.log('removing:', heap.remove());
console.log(heap.data.map(item => item.priority));
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment