## Saturday, 18 July 2015

### HeapSort

Heap sort is very easy to implement and its time complexity is O(n log(n)).

#### Sorting Min-heap:

1. Let array S is of size n. where  n is no of element to sort
2. top=1
3. Pop root from heap and put it at S[top]
4. top=top+1
5. heapify(A,1) //Heapify remaining heap again
6. Repeate step 3 to 5 untill heap is empty.

## C++ Program for HeapSort

1. //HeapSort
2. //complexivity O(nlogn)
3. #include<iostream>
4. #include<new>
5. using namespace std;
6. void BuildHeap(int *heap,int heapSize);
7. void hepify(int *heap,int i,int heapSize);
8. void HeapSort(int *heap,int *SortedArray,int &heapSize);
9. main(){
10. //initialise array of required heap size
11.     int heapSize;
12.     cout<<"Enter max element to sort:- "<<endl;
13.     cin>>heapSize;
14.     int *heap;
15.     heap =new int[heapSize+1];
16.     heap=0;
17.     //now insert all element in heap
18.     //after that we hepify it
19.     cout<<"Enter element of heap :"<<endl;
20.     //int a;
21.     for(int i=1;i<=heapSize;i++){
22.         cin>>heap[i];
23.     }
24.     BuildHeap(heap,heapSize); //make it heap
25.
26.     //Heap Sorting
27.     int *SortedArray;
28.     int n;
29.     n=heapSize;
30.     SortedArray = new int[heapSize];
31.     HeapSort(heap,SortedArray,heapSize);
32.     cout<<\nSorted Data by Heapsort :"<<endl;
33.     for(int i=0;i<n;i++){
34.         cout<<SortedArray[i]<<" ";
35.     }
36. }
37. void BuildHeap(int *heap,int heapSize){
38.      //heapify all node
39.     for(int i=heapSize/2;i>=1;i--){
40.         hepify(heap,i,heapSize);
41.     }
42. }
43. void hepify(int *heap,int i,int heapSize){
44.     int left=2*i; //index of left child of ith node
45.     int right=left+1; //index of right child of ith node
46.     int largest;
47.     //find index of largest among (ith node and its left and right child)
48.     if(left<=heapSize && heap[left]>heap[i])
49.         largest=left;
50.     else
51.         largest=i;
52.     if(right<=heapSize && heap[right]>heap[largest])
53.         largest=right;
54.     //now swap largest with ith node
55.     if(largest !=i){
56.         int temp =heap[i];
57.         heap[i]=heap[largest];
58.         heap[largest]=temp;
59.         hepify(heap,largest,heapSize);
60.     }
61. }
62. void HeapSort(int *heap,int *SortedArray,int &heapSize){
63.     //store root node at end of sorted array
64.     //change value of root node equal to value of last node of heap
65.     //then remove heap
66.     //Again apply BuiltHeap & repeat process until all nodes removed
67.     if(heapSize>=1){
68.         SortedArray[heapSize-1]=heap;
69.         heap=heap[heapSize];
70.         heapSize--; // basically removing last node
71.
72.         hepify(heap,1,heapSize); //again hepify to maintain heap property
73.         HeapSort(heap,SortedArray,heapSize);
74.     }
75. } Heap Sort

#### 1 comment:

1. Thank you so much for writing keep up like this.

THANKS FOR UR GREAT COMMENT

Blogger Widgets