GATE CS 2015 Set 2 Q.27 (CS Q.17): Binary Heaps and Priority Queues

Consider a complete binary tree where the left and the right subtrees of the root are max-heaps. The lower bound for the number of operations to convert the tree to a heap is

$\Omega(\log n)$

$\Omega(n)$

$\Omega(n \log n)$

$\Omega(n^2)$

Official answer and solution

Official answer: A
From: Official GATE 2015 answer key

Solution

Analyze the time complexity of the standard max-heapify procedure when the root's left and right subtrees are already max-heaps.

When both left and right subtrees of a complete binary tree are already valid max-heaps, only the root element may violate the max-heap property.

Restoring the heap property requires running max-heapify on the root node:

Compare the root with its left and right children.
Swap the root with the larger child if necessary.
Recurse down the affected subtree.

In the worst case (e.g., when the root value is the absolute minimum of the entire tree), the element must trickle down along a path from the root to a leaf node.

In a complete binary tree with $n$ nodes, the height of the tree is $h = \lfloor \log_2 n \rfloor$ . At each level, at most 2 comparisons and 1 swap are performed. Therefore, the worst-case number of operations is proportional to the tree height:

\Omega(\log n).

Final answer

Common trap

Confusing building a heap from an arbitrary array ( $O(n)$ ) with restoring the heap property at the root when subtrees are already valid heaps ( $O(\log n)$ ).

The answer is the one in the official GATE answer key. The solution is this site's own explanation.

Source

Paper: GATE 2015 Computer Science and Information Technology (CS) Session 2
Question: 27 of 65, printed as CS Q.17
Section: Computer Science and Information Technology

Report an error in this question

GATE questions are the work of the organising institutes. This site is independent and is not affiliated with them.

Question

Solution

Source