• + 0 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.