Question:
Let \( n \) be an odd number greater than 100. Consider a binary minheap with \( n \) elements stored in an array \( P \) whose index starts from 1.Which of the following indices of \( P \) do/does NOT correspond to any leaf node of the minheap?
Let \( n \) be an odd number greater than 100. Consider a binary minheap with \( n \) elements stored in an array \( P \) whose index starts from 1.
Which of the following indices of \( P \) do/does NOT correspond to any leaf node of the minheap?
Show Hint
In a 1-indexed n-element array heap, internal nodes are indices 1 to floor(n/2); leaves are everything after that. For odd n, floor(n/2) = (n-1)/2.
Updated On: Jul 22, 2026
- \( \dfrac{n+1}{2} \)
- \( \dfrac{n-1}{2} \)
- \( \dfrac{n-3}{2} \)
- \( n \)
Show Solution
Verified By Collegedunia
The Correct Option is B, C
Solution and Explanation
Step 1: Recall the standard leaf-node rule for an array-based binary heap.
For a heap with n elements in a 1-indexed array P, the children of the node at index i are at indices 2i and 2i+1. A node at index i is an INTERNAL (non-leaf) node if it has at least one child, i.e. if \( 2i \leq n \), equivalently \( i \leq \lfloor n/2 \rfloor \). So a node is a LEAF exactly when \( i > \lfloor n/2 \rfloor \), i.e. leaf indices run from \( \lfloor n/2 \rfloor + 1 \) up to n.
For a heap with n elements in a 1-indexed array P, the children of the node at index i are at indices 2i and 2i+1. A node at index i is an INTERNAL (non-leaf) node if it has at least one child, i.e. if \( 2i \leq n \), equivalently \( i \leq \lfloor n/2 \rfloor \). So a node is a LEAF exactly when \( i > \lfloor n/2 \rfloor \), i.e. leaf indices run from \( \lfloor n/2 \rfloor + 1 \) up to n.
Step 2: Simplify \( \lfloor n/2 \rfloor \) using that n is odd.
Since n is odd, \( n = 2k+1 \), so \( \lfloor n/2 \rfloor = k = \frac{n-1}{2} \). Therefore leaf indices run from \( \frac{n-1}{2}+1 = \frac{n+1}{2} \) up to n, and internal-node indices run from 1 to \( \frac{n-1}{2} \).
Since n is odd, \( n = 2k+1 \), so \( \lfloor n/2 \rfloor = k = \frac{n-1}{2} \). Therefore leaf indices run from \( \frac{n-1}{2}+1 = \frac{n+1}{2} \) up to n, and internal-node indices run from 1 to \( \frac{n-1}{2} \).
Step 3: Sanity-check with n = 101 (odd, greater than 100).
\( \lfloor 101/2 \rfloor = 50 \). Indices 1 to 50 are internal, indices 51 to 101 are leaves. Node 50's children are at 100 and 101 (both valid, so internal); node 51's children would be at 102 and 103 (both out of range, so leaf). This matches the derived range.
\( \lfloor 101/2 \rfloor = 50 \). Indices 1 to 50 are internal, indices 51 to 101 are leaves. Node 50's children are at 100 and 101 (both valid, so internal); node 51's children would be at 102 and 103 (both out of range, so leaf). This matches the derived range.
Step 4: Test option (A), index \( \frac{n+1}{2} \).
For n=101 this is 51, inside the leaf range [51,101]. So it DOES correspond to a leaf; not selected.
For n=101 this is 51, inside the leaf range [51,101]. So it DOES correspond to a leaf; not selected.
Step 5: Test option (B), index \( \frac{n-1}{2} \).
For n=101 this is 50, in the internal-node range [1,50]. So it does NOT correspond to a leaf; SELECTED.
For n=101 this is 50, in the internal-node range [1,50]. So it does NOT correspond to a leaf; SELECTED.
Step 6: Test option (C), index \( \frac{n-3}{2} \).
For n=101 this is 49, also strictly inside [1,50]. So it does NOT correspond to a leaf; SELECTED.
For n=101 this is 49, also strictly inside [1,50]. So it does NOT correspond to a leaf; SELECTED.
Step 7: Test option (D), index n.
The very last index of the array is always the last node in level order and can never have a child within the array bounds, so index n is always a leaf; not selected.
The very last index of the array is always the last node in level order and can never have a child within the array bounds, so index n is always a leaf; not selected.
Step 8: Conclusion.
The indices that do NOT correspond to a leaf node are \( \frac{n-1}{2} \) (option B) and \( \frac{n-3}{2} \) (option C).
\[ \boxed{\text{Options (B) and (C)}} \]The indices that do NOT correspond to a leaf node are \( \frac{n-1}{2} \) (option B) and \( \frac{n-3}{2} \) (option C).
Was this answer helpful?
0
0
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);
View More Questions
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 ?
View More Questions