Register

GATE CSE 2024 | Set 1 | Question: 31

• retagged by
2,725 views
2 votes
2 votes

​​​​​An array $[82,101,90,11,111,75,33,131,44,93]$ is heapified. Which one of the following options represents the first three elements in the heapified array?

  1. $82,90,101$
  2. $82,11,93$
  3. $131,11,93$
  4. $131,111,90$
• retagged by
User Avatar

1 Answer

2 votes
2 votes

1. Heapify node with value 111. Nothing changes as max-heap property is already satisfied.

2. Heapify node with value 11. Now 11 is swapped with 131 so that max-heap property is satisfied. (blue colored text in image).

3. Heapify node with value 90. Nothing changes as max-heap property is already satisfied.

4. Heapify node with value 101. Now 101 is swapped with 131 so that max-heap property is satisfied. (red colored text in image)

5. Heapify node with value 82. Now 82 is swapped with 131, then 82 is swapped with 111, then 82 is swapped with 93 so that max-heap property is satisfied. (green colored text in image)

Final array - $[131, 111, 90, 101, 93, 75, 33, 11, 44, 82]$

Answer - D

User Avatar
Voting & Accepting an answer helps improve the community
Answer:
← PreviousNext →
← Previous in categoryNext in category →

Related questions

3.8k
views
1 answers
4 votes
Arjun asked Feb 16
3,835 views
GATE CSE 2024 | Set 1 | Question: 7
Given an integer array of size $N$, we want to check if the array is sorted (in either ascending or descending order). An algorithm solves this problem by making a single pass through the array and comparing each element of the array only with its adjacent elements. The ... $\Omega(N)$ but not $\mathrm{O}(N)$ neither $\mathrm{O}(N)$ nor $\Omega(N)$
Given an integer array of size $N$, we want to check if the array is sorted (in either ascending or descending order). An algorithm solves this problem by making a single...
User Avatar
2.5k
views
3 answers
4 votes
Arjun asked Feb 16
2,461 views
GATE CSE 2024 | Set 1 | Question: 32
Consider the following recurrence relation: $T(n)=\left\{\begin{array}{c}\sqrt{n} T(\sqrt{n})+n \text { for } n \geq 1, \\ 1 \quad \text { for } n=1\end{array}\right.$ Which one of the following options is CORRECT? $T(n)=\Theta(n \log \log n)$ $T(n)=\Theta(n \log n)$ $T(n)=\Theta\left(n^2 \log n\right)$ $T(n)=\Theta\left(n^2 \log \log n\right)$  
Consider the following recurrence relation:$T(n)=\left\{\begin{array}{c}\sqrt{n} T(\sqrt{n})+n \text { for } n \geq 1, \\ 1 \quad \text { for } n=1\end{array}\right.$Whic...
User Avatar
3.7k
views
2 answers
4 votes
Arjun asked Feb 16
3,666 views
GATE CSE 2024 | Set 1 | Question: 35
Let $G$ be a directed graph and $T$ a depth first search $\text{(DFS)}$ spanning tree in $G$ that is rooted at a vertex $v$. Suppose $T$ is also a breadth first search $\text{(BFS)}$ tree in $G$, rooted at $v$. Which of the following ... the tree $T$ There are no forward-edge in $G$ with respect to the tree $T$ The only edges in $G$ are the edges in $T$
​​​​Let $G$ be a directed graph and $T$ a depth first search $\text{(DFS)}$ spanning tree in $G$ that is rooted at a vertex $v$. Suppose $T$ is also a breadth fir...
User Avatar
223
views
1 answers
0 votes
Ramayya asked Jan 7
223 views
ISRO 2024
Worst case time complexity of heap sort for n elements O(nlogn) O(logn) O^2 O(n)
Worst case time complexity of heap sort for n elementsO(nlogn)O(logn)O^2O(n)
User Avatar
Link Copied!