data structures using heapsort(arrn heap sort we have discussed binary heaps in thereforewe already know how to build heap from an arrayhow to insert new element in an already existing heapand how to delete an element from nowusing these basic conceptswe will discuss the application of heaps to write an efficient algorithm of heap sort (also known as tournament sortthat has running time complexity of ( log nfigure algorithm for heap sort given an array arr with elementsthe heap sort algorithm can be used to sort arr in two phasesin phase build heap using the elements of arr in phase repeatedly delete the root element of the heap formed in phase in max heapwe know that the largest value in is always present at the root node so in phase when the root element is deletedwe are actually collecting the elements of arr in decreasing order the algorithm of heap sort is shown in fig step [build heap hrepeat for to - call insert_heap(arrnarr[ ][end of loopstep (repeatedly delete the root elementrepeat while ncall delete_heap(arrnvalset [end of loopstep end complexity of heap sort heap sort uses two heap operationsinsertion and root deletion each element extracted from the root is placed in the last empty location of the array in phase when we build heapthe number of comparisons to find the right location of the new element in cannot exceed the depth of since is complete treeits depth cannot exceed mwhere is the number of elements in heap thusthe total number of comparisons (nto insert elements of arr in is bounded asg( < log hencethe running time of the first phase of the heap sort algorithm is ( log nin phase we have which is complete tree with elements having left and right sub-trees as heaps assuming to be the root of the treereheaping the tree would need comparisons to move one step down the tree since the depth of cannot exceed (log )reheaping the tree will require maximum of log comparisons to find the right location of in since elements will be deleted from heap hreheaping will be done times thereforethe number of comparisons to delete elements is bounded ash( < log hencethe running time of the second phase of the heap sort algorithm is ( log neach phase requires time proportional to ( log nthereforethe running time to sort an array of elements in the worst case is proportional to ( log nthereforewe can conclude that heap sort is simplefastand stable sorting algorithm that can be used to sort large sets of data efficiently programming example write program to implement heap sort algorithm #include #include #define max