Register

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

230 views
5 5 votes

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 are still in the heap?

1 Answer

1 1 vote

In heap sort using a max-heap, the array is divided into two parts:

  1. The left part is the active heap.
     
  2. The right part is the sorted region.

The largest elements move to the end of the array one by one.

Here, the last two elements are:

$8, 9$

They are already in sorted order and are no longer part of the heap.

Now check the remaining left part:

$[7, 3, 6, 2, 1, 4, 5]$

This is a valid max-heap:

  • $7 \geq 3$ and $7 \geq 6$
     
  • $3 \geq 2$ and $3 \geq 1$
     
  • $6 \geq 4$ and $6 \geq 5$
     

So, the active heap has $7$ elements.

Answer: $\boxed{7}$

Voting & Accepting an answer helps improve the community
Answer:
← Previous · GO Classes DPP | GAT...Next → · GO Classes CS/DA Tes...
← Previous in category · GO Classes DPP | GAT...Next in category → · GO Classes DPP | GAT...
Position:
Show:

Related questions

4 4 votes
1 1 answer
199
199 views
GO Classes asked Jul 21
199 views
GO Classes DPP | GATE CS, DA | Data Structure | Heap Sort
A max-heap is stored using $0$-based indexing as:$$[60, 30, 45, 15, 5, 10, 20]$$During the first iteration of heap sort:Swap the root with the last element. Reduce the he...
5 5 votes
2 2 answers
203
203 views
GO Classes asked Jul 21
203 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
192
192 views
GO Classes asked Jul 21
192 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
185
185 views
GO Classes asked Jul 21
185 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...