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.
Why not use a heap (PriorityQueue in Java) to remove the need for the O(nlog(n)) operation of sorting the array. Adding to a heap is O(log(n)) in worst-case, but O(1) in the average case. Since that happens n times, it should be faster on average. See my implementation:
// Complete the luckBalance function below.staticintluckBalance(intk,int[][]contests){intnumLuck=0;inttotalImportant=0;PriorityQueue<Integer>minHeap=newPriorityQueue<Integer>(newComparator<Integer>(){@Overridepublicintcompare(Integerobj1,Integerobj2){returnobj1-obj2;}});for(int[]contest:contests){numLuck+=contest[0];if(contest[1]==1){minHeap.offer(contest[0]);totalImportant++;}}for(inti=0;i<totalImportant-k;i++){numLuck-=2*minHeap.poll();}returnnumLuck;}
You will be adding n elements to your heap. For each insert it is logn and therefore for n elements, it would be n * log n. No difference is performance. Since there won't be anymore addition/deletion after the sort, it would not make any difference to choose heap over list.
As mentioned elsewhere, the heap should be kept at k. Average case, insertion is O(1), so the average case complexity of the overall luck balance algorithm in O(n). Worst case is O(nlogk). Therefore, only in the worst case scenario, and also when k=n, does the algorithm implementing the heap perform the same as the sort. In all other cases, the heap outperforms.
Luck Balance
You are viewing a single comment's thread. Return to all comments →
Why not use a heap (PriorityQueue in Java) to remove the need for the O(nlog(n)) operation of sorting the array. Adding to a heap is O(log(n)) in worst-case, but O(1) in the average case. Since that happens n times, it should be faster on average. See my implementation:
You will be adding n elements to your heap. For each insert it is logn and therefore for n elements, it would be n * log n. No difference is performance. Since there won't be anymore addition/deletion after the sort, it would not make any difference to choose heap over list.
Instead of letting the heap grow, keep it at size k. Now, each insert is logk instead of logn, and the total complexity is therefore nlogk.
As mentioned elsewhere, the heap should be kept at k. Average case, insertion is O(1), so the average case complexity of the overall luck balance algorithm in O(n). Worst case is O(nlogk). Therefore, only in the worst case scenario, and also when k=n, does the algorithm implementing the heap perform the same as the sort. In all other cases, the heap outperforms.