July 20, 2009

Member Rating

Curriki Rating**'P'** - This is a trusted Partner resource P**'P'** - This is a trusted Partner resource

The resource has been added to your collection

The heap sort involves the TREE (data structure) as the basic element to store a list.

- Career & Technical Education > General
- Mathematics > General
- Science > General

- Grade 11
- Grade 12
- Higher Education
- Graduate
- Undergraduate-Upper Division
- Undergraduate-Lower Division

Curriki Rating**'P'** - This is a trusted Partner resource P **'P'** - This is a trusted Partner resource

Not Rated Yet.

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.

Or

Our Terms of Service and Privacy Policies have changed. By logging in, you agree to our updated Terms and Policies.

Are you sure you want to logout?

Or