Chapter 17, Problem 28RE

Explanation of Solution

Heap sort algorithm:

• Step-1: Build the binary tree with the given elements.
• Step-2: Heapify the tree into either max-heap or min-heap.
  • Step-2.1: In max-heap, the parent nodes are greater than the child nodes, and in min-heap, parent nodes are lesser than the child nodes.
• Step-3: Swap the root node of the tree with the last leaf node.
• Step-4: Delete the leaf node and insert into the list from the last.
• Step-5: Repeat the steps 2, 3, and 4 until all nodes are deleted from the binary tree.

To sort the array:

Given elements are listed below,

0	1	2	3	4	5	6	7	8	9
11	27	8	14	45	6	24	81	29	33

To build a binary tree:

• Assume that the first element as the root node.
• If indexing of the elements starts from “0” then left child is considered as “2*i+1” and right child is considered as “2*i+2”.
• If indexing starts from “1” then the left child is considered as “2*i”, and right child is considered as “2*i+1”.
• The constructed binary tree is as follows,

To heapify the tree:

Construct a max-heap for this exercise.

• For max-heap, the parent nodes are greater than the child nodes.
• The tree after heapified is as follows,

• Swap the root node with the last leaf node as follows,

• Delete the last leaf node from the tree and insert to the list at the last as follows,

0	1	2	3	4	5	6	7	8	9
11	45	24	29	33	6	8	14	27	81

• Again heapify the tree as follows,

• Swap the root node with the last leaf node as follows,

• Delete the last leaf node from the tree and insert to the list as follows,

0	1	2	3	4	5	6	7	8	9
27	33	24	29	11	6	8	14	45	81

• Again heapify the tree as follows,

• Swap the root node with the last leaf node as follows,

• Delete the last leaf node from the tree and insert to the list at the last as follows,

0	1	2	3	4	5	6	7	8	9
11	45	24	29	33	6	8	33	45	81

• Again heapify the tree as follows,

• Swap the root node with the last leaf node as follows,

• Delete the last leaf node from the tree and insert to the list at the last as follows,

0	1	2	3	4	5	6	7	8	9
8	27	24	14	11	6	29	33	45	81

• Again heapify the tree as follows,