For a heap, what is the time complexity of both insert and extract-min/max operations in a binary heap?

For a heap, what is the time complexity of both insert and extract-min/max operations in a binary heap?

• A. O(1) for both.
• B. O(log n) for insert and O(1) for extract.
• C. O(log n) for both insert and extract.
• D. O(n) for both.

Answer: (D)

The key idea is that a binary heap is a nearly complete binary tree, so its height is about log2(n). Each operation can only move along a path from the root to a leaf or vice versa, so the work isn’t proportional to n but to the height of the heap. For inserting, you place the new element at the bottom to maintain the complete tree shape, then bubble it up by swapping with its parent until the heap property holds. This bubbling can happen at most one level at a time along a path from bottom to top, so the number of swaps is bounded by the height of the tree, which is O(log n). For extracting the minimum (in a min-heap) or maximum (in a max-heap), you remove the root and move the last element to the root, then restore the heap property by sifting that element down. It swaps with a child to move down the tree, again along a path no longer than the height, giving O(log n) time. So, both insert and extract-min/max have worst-case time complexity O(log n). The other options would imply linear or constant-time work, which doesn’t align with the way the heap’s height governs these operations.

The key idea is that a binary heap is a nearly complete binary tree, so its height is about log2(n). Each operation can only move along a path from the root to a leaf or vice versa, so the work isn’t proportional to n but to the height of the heap.

For inserting, you place the new element at the bottom to maintain the complete tree shape, then bubble it up by swapping with its parent until the heap property holds. This bubbling can happen at most one level at a time along a path from bottom to top, so the number of swaps is bounded by the height of the tree, which is O(log n).

For extracting the minimum (in a min-heap) or maximum (in a max-heap), you remove the root and move the last element to the root, then restore the heap property by sifting that element down. It swaps with a child to move down the tree, again along a path no longer than the height, giving O(log n) time.

So, both insert and extract-min/max have worst-case time complexity O(log n). The other options would imply linear or constant-time work, which doesn’t align with the way the heap’s height governs these operations.