What is the time complexity to extract the maximum element from a binary max-heap of n elements?
Show answer
O(log n)
After removing the root (the maximum), the heap must be restored (heapified) by bubble-down operations, which can take up to the height of the tree, or log n.
Also asked as:
- What is the Big O time complexity for removing the root and restoring the heap property in a binary max-heap of size n?