Heap Sort in Data Structures

Heap Sort

  Building Heap  

1. start with just one, element one element will always, satisfy heap property.
2. Insert next elements and make this a heap
3. Repeat step b until all elements are include in the heap

  Sorting  

2. Exchange the root name the last element in the heap
3. Make this a heap agar, but this time do not include the last node.
4. Repeat step a and b until there is no element left

Example

set the following elements in ascending order using heap sort 4,8,9,5.6   A

Build Heap

Sorting

    Program : Implementation of Heap Sort # include<stdio.h> void Heapsort(int a[],int n); void Build Heap(int a[],int n); void Reheap(int a[],int k); void main() { in a[20],n,i; printf(“Enter N value \n”); scanf(“%d”,&n); printf(“Enter those numbers: \n”); for(int i=1; i<=n; i++) { scanf(“%d”,&a[i]); } Heap sort(a,n); printf(“ The following are the sorted elements. \n”); for(i=1;i<=n;i++) { printf(“%d”,a[i]); } } void Heap sort(int a[],int n) { int fs,temp; Build Heap(a,n); for(pos=n;pos>=2;pos--) { temp=a[1]; a[1]=a[pos]; a[pos]=temp; Reheap(a,pos-1); } } void Build Heap(int a[],int n) { for(j=2;j<=n;j++) { key=a[i]; i=j/2; while((i>0) && (a[i]<key)) { a[j]=a[i]; j=i; i=j/2; } a[j]=key; } a[j]=key; } } void Reheap(int a[], int k) { int parent, child, key, heap; parent=1; child=2; Key=a[parent]; heap=0; while((child<=k) && (!heap)) { if(child<k) { if(a[child+1]>a[child]) child=child+1; } if(a[child]>key) { a[parent]=a[child]; parent=child; child=parent*2; } else { heap=1; } } a[parent]=key; }  

Time complexity :

Since each phase require time proportional to nlog₂n, The running time to sort the n-element array using heap sort is proportional to nlog₂n, that is f(n)=0(nlog₂n) the average running time of heap sort is o(nlog₂n)