Project ForgeData Structures
Trees
GATE 2007
Hard
Consider the process of inserting an element into a Max Heap, where the Max Heap is represented by an array. Suppose we perform a binary search on the path from the new leaf to the root to find the position for the newly inserted element, the number of comparisons performed is:
- AΘ(log₂ n)
- Θ(log₂ log₂ n)
- CΘ(n)
- DΘ(n log₂ n)
Explanation
The path from the new leaf to the root has length Θ(log₂ n) (the heap's height). Performing a BINARY SEARCH along this already-sorted (heap-ordered) path of length Θ(log n) takes Θ(log(log n)) = Θ(log₂ log₂ n) comparisons, instead of the Θ(log n) comparisons a linear walk up the path would need.
Source: GATE CS 2007 (2007)
This question is part of a 15-day revision cycle — sign in and Project Forge will bring it back the day before you'd forget it.