Heapsort Comparisons

Question

How many element comparisons would heap sort use to sort the integers $1$ to $8$ if they were

1. initially in sorted order,  
2. initially in reverse sorted order?

Comments

From the booklet i have choose this  question  .

Answer was mentioned as 24 for both the cases.

I don't know how

---

excellent question to clear concepts specially heapify.

if you want to solve it on your own youtube ravindra raula sir video on heaps will be very helpful

Answer 1

Say u r talking about min heap

$I)$ For initially sorted order number of comparison will be $0$

$II)$ For reverse sorted order

for level $1$ (i.e. at root) number of comparison will be $0$

for level $2$ number of comparison for each element will be $1$

for level $3$ number of comparison for each element will be $2$

for level $4$ number of comparison for each element will be $3$

So, total number of comparison will be $0+1+1+2+2+2+2+3=13$

Now, to sort elements , we need to count first sortest element, 2nd shortest element like below logic 

https://gateoverflow.in/269595/madeeasy-subject-test-2019-programming-%26-ds-heap

Which takes $0+1+2+3+2+2+1=11$

So, total comparison will be $11+13=24$

//Similar thing happens for max heap too

Comments

@Shaik Masthan

plz chk now

In case of decreasing order, I first have inserted one after another element in decreasing order, then applied heapify for each insertion. Then applied below logic for sorting sequence

chk this:https://gateoverflow.in/269595/madeeasy-subject-test-2019-programming-%26-ds-heap

is it ok??

 

---

@smsubham pointed out right that heap sort is not adaptive algorithm so it does not know that array is already sorted so it will first try to make it min heap but as it is already a min heap so number of comparision heapify will take to verify is 7 then 17 comparision will be needed to sort the array hence in total it will take 24 comparisions to sort the array

---

How level 3 has 2 comparisons? Level 3 will be having 4 elements so comparisons should be 3. Please explain, I’m not understanding

Answer 2

in first case here nlgn time will take here  and in second case also nlgn comparisons will take here

Comments

I am asking exact number of comparisons

Answer 3

check this link...

input 1 to 8 seperated by space...

for this number of comparisons is 27

 

input 8 to 1 seperated by space

for this number of comparisons is 24

https://www.google.com/url?sa=t&source=web&rct=j&url=http://www.allisons.org/ll/AlgDS/Sort/Heap/&ved=2ahUKEwjR3rCEuqjnAhX6xzgGHX-gC-kQFjABegQIDhAG&usg=AOvVaw1o1F4DS_PR2EydboEsaXDD&cshid=1580289366514