Let \(H\) be a binary min-heap consisting of \(n\) elements implemented as an array. What is the worst case time complexity of an optimal algorithm to find the maximum element in \(H\)?
Show Hint
- \(\Theta(1)\)
- \(\Theta(\log n)\)
- \(\Theta(n)\)
- \(\Theta(n \log n)\)
The Correct Option is C
Solution and Explanation
Step 1: Understanding properties of a min-heap.
In a binary min-heap, the minimum element is always stored at the root. However, there is no ordering guarantee among sibling or leaf nodes with respect to the maximum element.
Step 2: Location of the maximum element.
The maximum element in a min-heap must be present among the leaf nodes. In the worst case, all leaf nodes must be examined to determine the maximum value.
Step 3: Time complexity analysis.
A binary heap with \(n\) elements has approximately \(\lceil n/2 \rceil\) leaf nodes. Scanning these nodes requires linear time. Hence, the worst case time complexity is \(\Theta(n)\).
Step 4: Conclusion.
Therefore, the correct answer is \(\Theta(n)\), corresponding to option (C).
Top GATE CS Programming and Data Structures Questions
- Which of the following sequences when stored in an array at locations A[1],..., A[10] forms a max-heap?
- Given N distinct elements in an array, determine the number of comparisons required to find the element which is not the largest:
Consider the following code:
main() { int x = 126, y = 105; { if (x > y) x = x - y; else y = y - x; } while (x != y) printf("%d", x); }- In a binary search tree with the following elements: \( 10, -4, 15, 13, 20, 5, 16, 19 \), the number of edges from node 19 to the root is?
Consider the following code:
int a; int arr[] = {30, 50, 10}; int *ptr = arr[10] + 1; a = *ptr; (*ptr)++; ptr = ptr + 1; printf("%d", a + arr[1] + *ptr);
Top GATE CS Questions
- Which of the following sequences when stored in an array at locations A[1],..., A[10] forms a max-heap?
- The Lucas sequence Ln is defined by the recurrence relation: Ln = Ln−1 + Ln−2, for n ≥ 3, with L1 = 1 and L2 = 3. Which one of the options given is TRUE?
- Which of the following fields of IP header is/are always modified by any router before it forwards to IP Packet ?
- Which one of the following CIDR profix exactly represent the range of IP addresses 10.12.2.0 to 10.12.3.255?
- Consider an ethernet segment whose transmission is \(10^8\) bits per second. Maximum segment length \(500\ m\), speed of the provocation media velocity is \(2 × 10^8\) meter per second. What is the minimum frame size in bits ?