- The heap sort works as its name suggests.
- It begins by building a heap out of the data set, and then removing the largest item and placing it at the end of the sorted array.
- After removing the largest item, it reconstructs the heap, removes the largest remaining item, and places it in the next open position from the end of the sorted array.
- This is repeated until there are no items left in the heap and the sorted array is full.
- Elementary implementations require two arrays – one to hold the heap and the other to hold the sorted elements.
- Heapsort inserts the input list elements into a heap data structure.
- The largest value (in a max-heap) or the smallest value (in a min-heap) are extracted until none remain, the values having been extracted in sorted order.
#include < iostream.h >
#include < conio.h >
int heapSize = 10;
void print(int a[]) {
for (int i = 0; i <= 9; i++) {
cout << a[i] << “-”;
}
cout << endl;
}
int parent(int i) {
if(i==1)
return 0;
if(i%2==0)
return ( (i / 2)-1);
else
return ( (i / 2));
}
int left(int i) {
return (2 * i) + 1;
}
int right(int i) {
return (2 * i) + 2;
}
void heapify(int a[], int i) {
int l = left(i), great;
int r = right(i);
if ( (a[l] > a[i]) && (l < heapSize)) {
great = l;
}
else {
great = i;
}
if ( (a[r] > a[great]) && (r < heapSize)) {
great = r;
}
if (great != i) {
int temp = a[i];
a[i] = a[great];
a[great] = temp;
heapify(a, great);
}
}
void BuildMaxHeap(int a[]) {
for (int i = (heapSize – 1) / 2; i >= 0; i–) {
heapify(a, i);
print(a);
}
}
void HeapSort(int a[]) {
BuildMaxHeap(a);
for (int i = heapSize; i > 0; i–) {
int temp = a[0];
a[0] = a[heapSize - 1];
a[heapSize - 1] = temp;
heapSize = heapSize – 1;
heapify(a, 0);
}
}
void main() {
int arr[] = {
2, 9, 3, 6, 1, 4, 5, 7, 0, 8};
HeapSort(arr);
print(arr);
}
