Programming and Data Structures · Binary Heaps · 1 mark · Multiple choice
A complete binary tree has max-heaps as the left and right subtrees of its root. Which lower bound describes operations to convert the whole tree to a heap in the worst case?
Only the root may violate the heap property. Sifting it down repairs the tree; in the worst case it travels to a deepest leaf, taking one step per level. A complete tree has Θ(log n) height, so the tight worst-case lower bound among the options is Ω(log n), A.
More Binary Heaps questions
GATE 2015 CS (CS3) Q30– Find the minimum number of interchanges needed to convert the level-order array…
GATE 2021 CS (CS2) Q12– A binary min-heap of n elements is stored in an array. Find the worst-case complexity of…
GATE 2026 CS (CS1) Q23– Let n be an odd number greater than 100. Consider a binary minheap with n elements stored…
GATE 2025 CS (CS1) Q35– The height of any rooted tree is defined as the maximum number of edges in the path from…
GATE 2024 CS (CS1) Q41– An array [82, 101, 90, 11, 111, 75, 33, 131, 44, 93] is heapified. Which one of the…
GATE 2024 CS (CS1) Q43– Consider a binary min-heap containing 105 distinct elements. Let k be the index (in the…