HEAP SORT





 

Heap Sort involves different functions. They are provided here in detail. I hope you will enjoy it.

First of all the "Max-heap" is an important function for manipulating max-heaps (those whose parent node is bigger than both of its child nodes). Its inputs are an array A and an index i into the array.When MAX-HEAP is called, it is assumed that the binary tree rooted at LEFT and RIGHT are max-heaps, but that A[i] may be smaller than the children, thus violating the max-heap property. The function of MAX-HEAP is to let the value at A[i] “float-down” in the max-heap so that the sub-tree rooted at the index 'i' becomes a max heap.






MAX-HEAP(A,i)

1. l <- Left(i)
2. r<- Right(i)
3. if l? heapsize[A] and A[l]>A[i]
4. then largest<-l
5. else largest<-i
6. if r?heap-size [A] and A[r]>A[largest]
7. then largest<-r
8. if largest not equal to i
9. then exchange A[i]?A[largest]
10. MAX-HEAP(A,largest)



At each step, the largest of the elements A[i], A[LEFT], A[RIGHT] are determined and its index is stored in largest. Then the sub-tree rooted at node i is a max-heap and the procedure terminates. Otherwise, one of the two children has the largest element, and A[i] is swapped with A[largest], which causes node i and its children to satisfy the max-heap property. The node indexed by largest, however, now has the original value A[i],and thus the sub-tree rooted at largest may violate the max-heap property. So, max-heap must be called recursively on that sub-tree.

We can use the procedure MAX-HEAP in a bottom-up manner to convert an array A[1...n], where in n=length[A], into a max-heap. The elements in sub-array A[(n/2+1)...n] are all leaves of the tree, and so each is a 1element heap to begin with. The procedure BUILD-MAX-HEAP goes through the remaining nodes of the tree and runs MAX-HEAP on each one.


BUILD-MAX HEAP(A)

1. Heapsize[A] <-length[A]
2. For i<-[length[A]/2 downto 1
3. Do MAXHEAP(A,i)



The heap-sort algorithm starts by using BUILD-MAX-HEAP to build a max-heap on the input array, where n=length[A]. Since the maximum element of the array is stored at the root A[1], it can be put into its correct final position by exchanging it with A[n]. If we now “discard” node n from the heap, we observe that A[1...n-1] can easily be made into a max heap. The children of the root remain max-heaps, but the new root element may violate the max-heap property. All that is needed to restore the max-heap property, however, in one call to max-heap(A,1),which leaves a max-heap in A[1...n-1]. The heap-sort algorithm then repeats this process for the max-heap of size n-1 down to heap of size 2.

HEAPSORT(A)

1. BUILD-MAX-HEAP(A)
2. For i<-length[A] downto 2
3. Do exchange A[1]?A[i]
4. Heapsize[A] <- heapsize[A]-1
5. MAXHEAP(A,1)

FUNCTION MAX-HEAP BUILD-MAX HEAP
HEAP SORT
COMPLEXITY O(n) O(log n)O(n log n)




 

So Here we complete the Heap-sort Algorithm.

For the complete C code You can refer this link which is uploaded by some other member.

Non-profit Tax ID # 203478467