heap sort in data structure
It is a much more efficient version of selection sort it also works by determining the largest element of the list, placing that at the end (or beginning) of the list then continuing with the rest of all list, by accomplishes this task efficiently by using a data structure called HEAP.
This is a special type of binary tree once the data list has been made into a heap the root node is generated to be large or smaller element when it is removed and placed at end of the list the heap is rearranged so the largest element remaining moves to root.
- Heap sort algorithm is based on the creation of max heap (to sort in ascending order). In a max heap, the largest element is root and all child are less than root
- It is based on deletion of root element and readjustment of the heap to restore heap property
- A process is carried out repeatedly to generate element in descending order
- Complexity of the heap sort: The heap sort time complexity is O(N log N)
| Worst case Time Complexity: O(N log N) |
Heap sort example
Heap sort program in c
| 123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105 | #include<stdio.h>#include<conio.h>#define N 7int a[N];void heap(int root, int size){int li=(root+1)*2-1,ri=li+1,mi,t;if(li<=size){ if(li==size) { mi=li; } else { mi=(a[li]>a[ri])?li:ri; } if(a[root]<a[mi]) { t=a[root]; a[root]=a[mi]; a[mi]=t; heap(mi,size); }}}void main(void){ int I,last,t; clrscr(); printf(“\n Enter the element:”); for(i=0;i<N;i++) { scanf(“%d”,&a[i]); } for(i=N/2-1;i>=0;i–) { heap(i,N-1); }for(i=0;last=N-1;i<N-1;i++,last–){ t=a[0]; a[0]=a[last]; a[last]==t; heap(0,last-1);}printf(“\n Sorted element :\n”);for(i=0;i<N;i++){ printf(“%d”\n”,a[i]);}getch();} |
Output:
Enter the element:
50
20
60
40
10
90
70
Sorted element :
10
20
40
50
60
70
90
Comment below if you are facing any problem in this heap sort in data structure.