You are viewing a single comment's thread. Return to all comments →
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.