|
| 1 | +classHeap{ |
| 2 | +constructor(stones){ |
| 3 | +this.heap=stones |
| 4 | +this.size=stones.length |
| 5 | +this.heapify(0) |
| 6 | +} |
| 7 | +right(pos){ |
| 8 | +return2*pos+2 |
| 9 | +} |
| 10 | +left(pos){ |
| 11 | +return2*pos+1 |
| 12 | +} |
| 13 | +isleaf(pos){ |
| 14 | +if(2*pos+1>=this.size)returntrue |
| 15 | +returnfalse |
| 16 | +} |
| 17 | +swap(a,b){ |
| 18 | +lettemp=this.heap[a] |
| 19 | +this.heap[a]=this.heap[b] |
| 20 | +this.heap[b]=temp |
| 21 | +} |
| 22 | +fix(pos){ |
| 23 | +if(this.isleaf(pos))return |
| 24 | +letleft=this.left(pos) |
| 25 | +letright=this.right(pos) |
| 26 | +letbigger=left |
| 27 | +if(right<this.size)bigger=this.heap[left]>this.heap[right] ?left :right |
| 28 | +if(this.heap[pos]<this.heap[bigger]){ |
| 29 | +this.swap(pos,bigger) |
| 30 | +this.fix(bigger) |
| 31 | +} |
| 32 | +} |
| 33 | +heapify(pos){ |
| 34 | +if(this.isleaf(pos))return |
| 35 | +this.heapify(this.left(pos)) |
| 36 | +this.heapify(this.right(pos)) |
| 37 | +this.fix(pos) |
| 38 | +} |
| 39 | +delete(){ |
| 40 | +this.swap(0,--this.size) |
| 41 | +this.fix(0) |
| 42 | +returnthis.heap[0] |
| 43 | +} |
| 44 | +insert(val){ |
| 45 | +this.size++ |
| 46 | +this.heap[this.size-1]=val |
| 47 | +this.heapify(0) |
| 48 | +} |
| 49 | +peek(){ |
| 50 | +returnthis.heap[0] |
| 51 | +} |
| 52 | +} |
| 53 | +/** |
| 54 | + *@param {number[]} stones |
| 55 | + *@return {number} |
| 56 | + */ |
| 57 | +varlastStoneWeight=function(stones){ |
| 58 | +//use a max heap to pop off the top 2 stones at each time |
| 59 | +//if result is 0 we can do nothing |
| 60 | +//if the result is a new weight we can push it back to the heap |
| 61 | +constheap=newHeap(stones) |
| 62 | +while(heap.size>1){ |
| 63 | +letx=heap.peek() |
| 64 | +heap.delete() |
| 65 | +lety=heap.peek() |
| 66 | +heap.delete() |
| 67 | +constres=x-y |
| 68 | +if(res>0)heap.insert(res) |
| 69 | +} |
| 70 | +if(heap.size)returnheap.peek() |
| 71 | +return0 |
| 72 | +}; |