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.
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 →
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.