• + 0 comments

    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.