| class Heap { | |
| constructor() { | |
| this.values = [] | |
| } | |
| bubbleUp() { | |
| let index = this.values.length - 1; | |
| let parentIndex = Math.floor((index - 1) / 2); | |
| while(this.values[parentIndex] < this.values[index]){ | |
| let temp = this.values[index]; | |
| this.values[index]= this.values[parentIndex]; | |
| this.values[parentIndex] = temp; | |
| index = parentIndex; | |
| parentIndex = Math.floor((index - 1) / 2); | |
| } | |
| } | |
| bubbleDown() { | |
| let index = 0; | |
| let leftChildIndex,rightChildIndex; | |
| while(true) { | |
| leftChildIndex = (2 * index) + 1; | |
| rightChildIndex = (2 * index) + 2; | |
| let swappedIndex = null; | |
| if(leftChildIndex < this.values.length) { | |
| if(this.values[leftChildIndex] > this.values[index]) { | |
| swappedIndex = leftChildIndex | |
| } | |
| } | |
| if(rightChildIndex < this.values.length) { | |
| if(swappedIndex && this.values[rightChildIndex] > this.values[swappedIndex]){ | |
| swappedIndex = rightChildIndex; | |
| } else if(!swappedIndex && this.values[rightChildIndex] > this.values[index]) { | |
| swappedIndex = rightChildIndex; | |
| } | |
| } | |
| if(swappedIndex) { | |
| let temp = this.values[index]; | |
| this.values[index] = this.values[swappedIndex]; | |
| this.values[swappedIndex] = temp; | |
| index = swappedIndex; | |
| } else { | |
| break; | |
| } | |
| } | |
| } | |
| extractMax() { | |
| let oldMax = this.values[0]; | |
| let newMax = this.values.pop(); | |
| if(this.values.length > 0) { | |
| this.values[0] = newMax; | |
| this.bubbleDown() | |
| } | |
| return oldMax | |
| } | |
| insert(value) { | |
| this.values.push(value); | |
| this.bubbleUp(); | |
| return this; | |
| } | |
| } | |
| let heap = new Heap() | |
| let inputs= [41,39,33,18,27,12,55] | |
| for(let v of inputs) { | |
| heap.insert(v) | |
| } |