Back to course home
0% completed
Vote For New Content
Incorrect time complexity for polling from the heap
Mykola Zhadanov
Nov 23, 2024
- Pop an item from the heap, which is
O(log(n)). - this is incorrect as we always poll Min (or Max), so it's always O(1) operation.
0
0
Comments
Comments
Design Gurusa year ago
The pop operation does take O(logN).
Why: The root element (min or max) is removed and replaced by the last element in the heap. Then, the heap property is restored by "bubbling down" (heapify-down), which also takes log n time in the worst case.
On this page