Course contentsShow
← Computer Science
Lesson 592 of 2,87214. Heaps and Priority QueuesFree lesson

Extract Time Complexity

Analyze O(log n) complexity of extract based on maximum downward path length.

Extract Time Complexity

You'll learn: Why extracting the root from a heap (Extract-Max or Extract-Min) runs in O(log n) time.

The Core Idea

When you extract the root element from a heap, you must restore the heap's order property. After swapping the last element to the root position, you perform downward bubbling (heapify-down) to sink it to its proper place. The time this takes depends on how far down the element might travel—which is limited by the heap's height.

Why O(log n)?

A binary heap stored in an array is a complete binary tree. This structure guarantees that the tree's height is always log₂(n), where n is the number of elements.

During downward bubbling:

  • At each level, you compare the element with its children (constant time: O(1))
  • You swap if needed (also O(1))
  • You move down one level

In the worst case, the element travels from the root all the way to a leaf—traversing the entire height of the tree. That's at most log n levels.

The Math

  • Heap height = ⌊log₂(n)⌋
  • Maximum number of swaps = height of tree
  • Work per level = O(1)
  • Total work = O(log n)

Analogy

Imagine a demotion ladder in a company with log n floors. An unqualified CEO (the last element promoted to root) might need to descend one floor at a time until reaching their proper rank. The maximum descent is the building's height—not the number of employees.

Key Takeaway: Extract operations run in O(log n) time because downward bubbling is bounded by the heap's height, which is logarithmic in the number of elements due to the complete binary tree structure.