Register

GO Classes DPP | GATE CS, DA | Data Structure | Heap Sort

189 views
4 4 votes

A max-heap is stored using $0$-based indexing as:

$$[60, 30, 45, 15, 5, 10, 20]$$

During the first iteration of heap sort:

  1. Swap the root with the last element.
     
  2. Reduce the heap size by $1$.
     
  3. Apply $\texttt{downHeap}$ on the remaining heap region.
     

What is the array after this first iteration?

  1. $[60, 30, 45, 15, 5, 10, 20]$
     
  2. $[45, 30, 20, 15, 5, 10, 60]$
     
  3. $[45, 30, 10, 15, 5, 20, 60]$
     
  4. $[30, 20, 45, 15, 5, 10, 60]$

1 Answer

1 1 vote

Initial max-heap:

Heap Array $:[60, 30, 45, 15, 5, 10, 20]$

First, swap the root with the last element.

Heap Array $:[20, 30, 45, 15, 5, 10, 60]$

Now $60$ is in the sorted region, so heapify only the active heap:

Heap Array $:[20, 30, 45, 15, 5, 10]$

Heapify-down starts from index $0$.

Children of $20$ are $30$ and $45$.

Since this is a max-heap, swap with the larger child $45$.

Heap Array $:[45, 30, 20, 15, 5, 10, 60]$

Now $20$ has only one child $10$ in the active heap. Since $20 > 10$, stop.

Final Heap Array $:[45, 30, 20, 15, 5, 10, 60]$
 

Answer: B

• edited by
Voting & Accepting an answer helps improve the community
Answer:
← Previous · GO Classes DPP | GAT...Next → · GO Classes DPP | GAT...
← Previous in category · GO Classes DPP | GAT...Next in category → · GO Classes DPP | GAT...
Position:
Show:

Related questions

5 5 votes
1 1 answer
224
224 views
GO Classes asked Jul 21
224 views
GO Classes DPP | GATE CS, DA | Data Structure | Heap Sort
During heap sort, the array looks like this:$J = [7, 3, 6, 2, 1, 4, 5, 8, 9]$Assume heap sort is using a max-heap to sort the array in increasing order.How many elements ...
5 5 votes
2 2 answers
197
197 views
GO Classes asked Jul 21
197 views
GO Classes DPP | GATE CS, DA | Data Structure | Insert in Max-Heap
The following max-heap is stored using $1$-based indexing:$[57, 53, 42, 48, 25, 34, 29, 18, 30, 25]$Insert $55$ into this max-heap. What is the final heap array?$[57, 55,...
5 5 votes
2 2 answers
184
184 views
GO Classes asked Jul 21
184 views
GO Classes DPP | GATE CS, DA | Data Structure | DeleteMin from Min-Heap
A min-heap is stored using $1$-based indexing as:$[2, 13, 7, 17, 14, 22, 8, 21]$After one $\texttt{DeleteMin}$ operation, what is the final heap array?$[7, 13, 8, 17, 14,...
7 7 votes
1 1 answer
178
178 views
GO Classes asked Jul 21
178 views
GO Classes DPP | GATE CS, DA | Data Structure | Binary Min-Heaps
Consider the following binary min-heap:Perform the following operations in order:$\text{DeleteMin}$ $\text{Insert 8}$ $\text{Insert 2}$ What is the final array representa...