USA: +1 (725) 712-1730 
Sign in
Request solve the following problem on “Alogrithms” The referred book is “Introduction to Alogrithms” by Thomas Cormen
![b) Using Fig. 6.4 in page 137 (page 161 in third edition of the book as a model, illustrate the operation of HEAPSORT on the array A 5,12,4,8,10,11,9,7,6]. 14 9 63de14176cd9113000fa4ccedd 9113000fa4cceddb 1175 A 1 2 3 47 8 9 10 14 16 Figure 6.4 The operation of HEAPSORT. (a) The max-hcap data structureust after BUILD-MAX HEAP has buil in line1. (b)-G) The max-heap just after each call of MAX-HEAPIFY in line 5, showing the value of at that time. Only lightly shaded nodes remain in the heap、(k) The resulting sorted aray A](https://d2vlcm61l7u1fs.cloudfront.net/media%2Ffe7%2Ffe78a2ce-ae69-4962-8845-3e76291e07cf%2Fphpst9BCq.png)
b) Using Fig. 6.4 in page 137 (page 161 in third edition of the book as a model, illustrate the operation of HEAPSORT on the array A 5,12,4,8,10,11,9,7,6]. 14 9 63de14176cd9113000fa4ccedd 9113000fa4cceddb 1175 A 1 2 3 47 8 9 10 14 16 Figure 6.4 The operation of HEAPSORT. (a) The max-hcap data structureust after BUILD-MAX HEAP has buil in line1. (b)-G) The max-heap just after each call of MAX-HEAPIFY in line 5, showing the value of at that time. Only lightly shaded nodes remain in the heap、(k) The resulting sorted aray A
Expert Answer
The steps are as follows:
The data is 5,12,4,8,10,11,9,7,6
We will go for max heap. The node will be lower than the nodes.
The tree created will be
Step 1
5
12 4
8 10 11 9
7 6
In this step our array is 5,12,4,8,10,11,9,7,6
Step 2. We will apply heapify to (9/2-1)= 3 index of the array
5
12 4
8 10 11 9
7 6
We don’t have to do any thing as 8 is ok.
array is 5,12,4,8,10,11,9,7,6
Step 3 . We will apply heapify to array index = 2, i.e 4
5
12 11
8 10 4 9
7 6
We have to swap 4 and 11
The array becomes 5,12,11,8,10,4,9,7,6
Step 4 We will apply heapify to array index 1 i.e 12
5
12 11
8 10 4 9
7 6
We don’t have to do anything as 12 is ok
Our array becomes 5,12,11,8,10,4,9,7,6
Step 5 We will apply heapify to array index 0 i.e 5
12
5 11
8 10 4 9
7 6
We need to swap 12 and 5 .
Our array becomes 12,5,11,8,10,4,9,7,6
Step 5. We need to check the tree now.
12
5 11
8 10 4 9
7 6
Step 6 We need to do certain adjustments now like swapping 5 and 10 so our tree bexomes:
12
10 11
8 5 4 9
7 6
our array becomes 12,10,11,8,5,4,9,7,6 (It is a max heap as all the node values are more than their children
Step 7 Now taking the root out of the tree we get:
11
10 9
8 5 4
7 6
12
Repeating step 7 we get
10
8 9
7 5 4
6
11 12
Repeating step 7 we get
9
8 4
7 5
6
10 11 12
Repeating step 7 we get
8
7 4
6 5
9 10 11 12
Repeating step 7 we get
7
6 4
5
8,9 10 11 12
Repeating step 7 we get
6
5 4
7 8 9 10 11 12
Repeating step 7 we get
5
4
6 7 8 9 10 11 12
Repeating step 7 we get
4
5 6 7 8 9 10 11 12
Repeating step 7 we get
4 5 6 7 8 9 10 11 12 (Our Sorted array)
