HEAPSORT eventually heap both the left and
HEAPSORT ALGORITHMFirst 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, 71Building the heap treeThe array represented as a tree, complete but not orderedSTEP118 97 10 1 88 71Inputted array that is not in order position.STEP 218 97 10 1 88 71Start 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 318 97 71 1 88 10While arranging the array3 the situation will be like thisSTEP 418 97 71 1 88 10Next comes array2 which is 97. Its children are smaller which are 71 and 1 so no transudation is neededSTEP 518 97 71 1 88 10The 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 697 18 71 1 88 10This 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.STEP797 88 71 1 18 10Now the binary heap is built the tree is in order position.Sorting – performing deleteMax operations:STEP888 71 1 18 1097 Delete the first element 97 Then store 97 in a temporary place. A space is created at the first left row.STEP988 71 1 88 9710 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.STEP1088 71 1 18 9710 Number 10 is transuded down leaving a space for number 18. And number 88 is moved to the right side of the array.STEP1188 18 71 1 9710 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)STEP1288 18 71 1 10 97Now number 10 can be inserted in the slotSTEP1318 71 1 10 9788 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.STEP1418 71 1 88 9710 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.STEP1571 18 1 88 9710 The element 10 is less than the children of the slot which element 71 so element 10 will percolate the space STEP1671 18 10 1 88 97Insert 10 element in the spaceSTEP1718 10 1 88 9771 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 topSTEP1818 10 71 88 971 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 arraySTEP1918 10 71 88 971 Percolate a hole since 1 cannot be inserted there because it is less than the children of the array element.STEP2018 1 10 71 88 97 Insert 1 in the allotted allotedSTEP211 10 71 88 9718 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.
STEP221 18 71 88 9710 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 arraySTEP2310 1 18 71 88 97Store element 10 in the space because 10 is greater than the children of the element which is 1STEP241 18 71 88 9710 DeleteMax the top element 10 and remove it from the heap and store it into a temporary location.STEP2510 18 71 88 971 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 arraySTEP261 10 18 71 88 97Place 1 in the space as it is the only remaining element in the heapSTEP271 10 18 71 88 97The array is now sorted since 1 is the last element from the heap0386080000-681736000