IN COLLECTION

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.

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.

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.

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.