Problem Detail: Which of the following strategies is more feasible?
- Strategy 1: Remove the element from the array, compress the array and reheapify.
- Strategy 2: Update the value of this node to the current maximum value in the heap + 1, then delete_max.
Asked By : envy_intelligence
Answered By : user1742364
I assume that “compress the array” means to shift the elements to the left until the gap is gone, right? Then strategy 2 is clearly better than strategy 1: While you have a worst case complexity of $mathcal{O}(n)$ in the first case (in the worst case, you need to shift every remaining element of the array to the left), you only need two “standard” heap operations in the second strategy, both of which only need $mathcal{O}(log n)$ time.
Best Answer from StackOverflow
Question Source : http://cs.stackexchange.com/questions/38278 Ask a Question Download Related Notes/Documents
