We use cookies to ensure you have the best browsing experience on our website. Please read our cookie policy for more information about how we use cookies.
classMinHeap{constructor(){this.arr=[];}left(i){return2*i+1;}right(i){return2*i+2;}parent(i){returnMath.floor((i-1)/2);}size(){returnthis.arr.length;}getMin(){returnthis.arr[0];}insert(k){letarr=this.arr;arr.push(k);// Fix the min heap property if it is violated, HeapifyUpleti=arr.length-1;// While newly pushed value is smaller than its parent node:while(i>0&&arr[this.parent(i)]>arr[i]){// Swap the new node and its parent node, then update i tobe its parent's indexletp=this.parent(i);[arr[i],arr[p]]=[arr[p],arr[i]];i=p;}}extractMin(){letarr=this.arr;if(arr.length==1){returnarr.pop();}// Store the minimum value, and remove it from heapletres=arr[0];arr[0]=arr[arr.length-1];arr.pop();// Reheapify the arr, HeapifyDownthis.MinHeapify(0);returnres;}// A recursive method to heapify a subtree with the root at given index// This method assumes that the subtrees are already heapifiedMinHeapify(i){letarr=this.arr;letn=arr.length;// Base case:if(n===1){return;}letl=this.left(i);letr=this.right(i);letsmallest=i;// Find the smallest itemif(l<n&&arr[l]<arr[i]){smallest=l;}if(r<n&&arr[r]<arr[smallest]){smallest=r;}// If this node is not the smallest, swap it with the smallest, then HeapifyDown againif(smallest!==i){[arr[i],arr[smallest]]=[arr[smallest],arr[i]]this.MinHeapify(smallest);}}}functioncookies(k,A){// Write your code hereconstheap=newMinHeap();A.forEach((item)=>{heap.insert(item);});letcount=0;while(heap.size()>1&&heap.getMin()<k){constleastValue=heap.extractMin();constsecondLeastValue=heap.extractMin();constnewValue=leastValue+(secondLeastValue*2);heap.insert(newValue);count++;}if(heap.size()===1&&heap.getMin()<k){return-1;}returncount;// let a = A;// let count = 0;// while (a.some(value => value < k)) {// if (a.length < 2) return -1;// const sortedA = a.sort((a, b) => a - b);// const newValue = sortedA[0] + (sortedA[1] * 2);// a.splice(0, 2, newValue);// count++;// }// return count;}
Cookie support is required to access HackerRank
Seems like cookies are disabled on this browser, please enable them to open this website
Jesse and Cookies
You are viewing a single comment's thread. Return to all comments →
JavaScript implementing MinHeap:
MinHeap class from GeeksforGeeks.