Project ForgeData Structures
Trees
GATE 2008
Medium
We have a binary heap on n elements and wish to insert n more elements (not necessarily one after another) into this heap. The total time required for this is
- AΘ(log n)
- BΘ(n)
- Θ(n log n)
- DΘ(n²)
Explanation
Each individual insertion into a heap of size up to 2n costs O(log n) in the worst case (bubbling up along the height of the heap). Performing n such insertions costs O(n log n) total.
Source: GATE CS 2008 (2008)
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.