Open glyh opened 2 years ago
In this solution, it says that the heap built on ascending sequences will experience worst heapify scenario. Can you provide a proof? Actually I can think of some counterexample, say we build heap on this sequence:
1 2 3 4 5 6 7
We got:
7 5 6 4 2 1 3
And when we pop 7, we got:
3 5 6 4 2 1
The "3" only needs to be heapify once:
6 5 3 4 2 1
Which is not the worst-case scenario.
In this solution, it says that the heap built on ascending sequences will experience worst heapify scenario. Can you provide a proof? Actually I can think of some counterexample, say we build heap on this sequence:
We got:
And when we pop 7, we got:
The "3" only needs to be heapify once:
Which is not the worst-case scenario.