HEAPSORT ALGORITHM

First thing to do is to arrange the nodes in the form of Binary Tree as per specific rule. It is the size of the heap within a specific limit inputted by the user. And then the program will generate a corresponding Binary Tree with nodes sustaining randomly generated key values. The program uses an operation called “Heapify”. This arranges the nodes in ascending order. The function of Heapify is to let the root which is “i” supersedes position by reciprocating itself with the larger of its subordinates or children. Whenever Heapify is called it will eventually heap both the left and right subtree of the “i” which is the root. For generating heap operation, we must consider the variables used. Since “FUN” is equivalent for the number of nodes in the tree and “i” corresponds to the key of a tree. It is crucial to identify each variable for the formula we are going to use. After generating heap operation, removing of maximum element is next the step. In this rule, program removes the largest element of the heap of the root by replacing it with the last element. The program executes Heapify (new root) so that the resulting tree gratify the heap property. Reprise the procedures from the top to end until the heap is completely empty.

EXPLANATIONS:

Here is sample the array: 18, 97, 10, 1, 88, 71

Building the heap tree

The array represented as a tree, complete but not ordered

STEP1

18 97 10 1 88 71

Inputted array that is not in order position.

STEP 2

18 97 10 1 88 71

Start with the rightmost node at height 1 – the node at position 3 = Size/2 because it has one child greater than parent so it has to be transuded.

STEP 3

18 97 71 1 88 10

While arranging the array3 the situation will be like this

STEP 4

18 97 71 1 88 10

Next comes array2 which is 97. Its children are smaller which are 71 and 1 so no transudation is needed

STEP 5

18 97 71 1 88 10

The last node to be processed is array 1 which is number 18. Its left child is the greater of the children which number 97 so item at array1which is number 18 has to be transuded to the left, replacing array2 which is number 97.

STEP 6

97 18 71 1 88 10

This is will be the arrangement.

The children of array2 which 1 and 88 are greater, and item 18 has to be moved further and substitute by array5 number 88.

STEP7

97 88 71 1 18 10

Now the binary heap is built the tree is in order position.

Sorting – performing deleteMax operations:

STEP8

88 71 1 18 10

97 Delete the first element 97 Then store 97 in a temporary place. A space is created at the first left row.

STEP9

88 71 1 88 97

10 Substitute 97 with the last element of the heap. The number 10 will be adjusted in the heap, it becomes a cell from the sorted array its and will no longer be a part of the heap.

STEP10

88 71 1 18 97

10 Number 10 is transuded down leaving a space for number 18. And number 88 is moved to the right side of the array.

STEP11

88 18 71 1 97

10 Allocate number 10 to the later position of 18 since it was moved to the space besides number 88 (10 is lesser than 18, so it cannot be inserted in the previous slot)

STEP12

88 18 71 1 10 97

Now number 10 can be inserted in the slot

STEP13

18 71 1 10 97

88 DeleteMax the top element 88. Drop down the maximum element which is number 88 and store it in a temporary place. A space is created at the top.

STEP14

18 71 1 88 97

10 Swap element 88 with the last element of the heap.

As 10 will be adjusted in the heap, its element will no longer be a part of the heap but it becomes an element from the sorted array.

STEP15

71 18 1 88 97

10 The element 10 is less than the children of the slot which element 71 so element 10 will percolate the space

STEP16

71 18 10 1 88 97

Insert 10 element in the space

STEP17

18 10 1 88 97

71 DeleteMax 71 meaning to say we need to drop down the maximum element which is number 71 and store it in a temporary place. A space is created at the top. A hole is created at the top

STEP18

18 10 71 88 97

1 After storing element 71 to a temporary place, swap 71 with the last element of the heap.

As 1 will be adjusted in the heap, its will no longer be a part of the heap instead it becomes an element from the sorted array

STEP19

18 10 71 88 97

1 Percolate a hole since 1 cannot be inserted there because it is less than the children of the array element.

STEP20

18 1 10 71 88 97

Insert 1 in the allotted alloted

STEP21

1 10 71 88 97

18 DeleteMax the top element 18. It means that 18 will be deleted and will be store in a temporary location. And then a space is created.

STEP22

1 18 71 88 97

10 Swap 18 with the last element of the heap.

As 10 will be adjusted in the heap, so it will no longer be a part of the heap instead it becomes an element from the sorted array

STEP23

10 1 18 71 88 97

Store element 10 in the space because 10 is greater than the children of the element which is 1

STEP24

1 18 71 88 97

10 DeleteMax the top element 10 and remove it from the heap and store it into a temporary location.

STEP25

10 18 71 88 97

1 Swap 10 with the last element of the heap. As 1 will be adjusted in the heap, its cell will no longer be a part of the heap instead it becomes an element from the sorted array

STEP26

1 10 18 71 88 97

Place 1 in the space as it is the only remaining element in the heap

STEP27

1 10 18 71 88 97

The array is now sorted since 1 is the last element from the heap

038608000

0-681736000