//
// main.cpp
// Heapsort
//
// Created by Himanshu on 25/09/21.
//
#include <iostream>
using namespace std;
void printArray (int arr[], int n) {
for (int i=0; i<n; i++) {
cout<<arr[i]<<" ";
}
cout<<endl;
}
void MaxHeapify(int arr[], int i, int heapSize) {
int l, r, large;
l = 2*i + 1;
r = 2*i + 2;
if (l < heapSize && arr[l] > arr[i]) {
large = l;
} else {
large = i;
}
if (r < heapSize && arr[r] > arr[large]) {
large = r;
}
//Assuring heap property
if (large != i) {
swap (arr[i], arr[large]);
MaxHeapify(arr, large, heapSize);
}
}
void BuildHeap(int arr[], int n) {
int k = (n/2)-1;
int j = 1;
for (int i=k; i>=0; i--) {
MaxHeapify(arr, i, n);
printf("Array after %d Max-Heapify\n", j++);
printArray(arr, n);
}
}
void Heapsort (int arr[], int n) {
BuildHeap(arr, n);
for (int i=n-1; i>=0; i--) {
swap(arr[0], arr[i]);
n--;
MaxHeapify(arr, 0, n);
}
}
int main() {
int arr[] = {8, 3, 9, 2, 16, 10, 14, 7, 4};
int n = sizeof(arr)/sizeof(arr[0]);
cout<<"Initial Array:"<<endl;
printArray(arr, n);
cout<<endl;
Heapsort(arr, n);
cout<<endl<<"Array after Heapsort:"<<endl;
printArray(arr, n);
return 0;
}
Ly8KLy8gIG1haW4uY3BwCi8vICBIZWFwc29ydAovLwovLyAgQ3JlYXRlZCBieSBIaW1hbnNodSBvbiAyNS8wOS8yMS4KLy8KCiNpbmNsdWRlIDxpb3N0cmVhbT4KdXNpbmcgbmFtZXNwYWNlIHN0ZDsKCnZvaWQgcHJpbnRBcnJheSAoaW50IGFycltdLCBpbnQgbikgewogICAgZm9yIChpbnQgaT0wOyBpPG47IGkrKykgewogICAgICAgIGNvdXQ8PGFycltpXTw8IiAiOwogICAgfQogICAgY291dDw8ZW5kbDsKfQoKdm9pZCBNYXhIZWFwaWZ5KGludCBhcnJbXSwgaW50IGksIGludCBoZWFwU2l6ZSkgewogICAgaW50IGwsIHIsIGxhcmdlOwogICAgbCA9IDIqaSArIDE7CiAgICByID0gMippICsgMjsKICAgIGlmIChsIDwgaGVhcFNpemUgJiYgYXJyW2xdID4gYXJyW2ldKSB7CiAgICAgICAgbGFyZ2UgPSBsOwogICAgfSBlbHNlIHsKICAgICAgICBsYXJnZSA9IGk7CiAgICB9CiAgICAKICAgIGlmIChyIDwgaGVhcFNpemUgJiYgYXJyW3JdID4gYXJyW2xhcmdlXSkgewogICAgICAgIGxhcmdlID0gcjsKICAgIH0KICAgIAogICAgLy9Bc3N1cmluZyBoZWFwIHByb3BlcnR5CiAgICBpZiAobGFyZ2UgIT0gaSkgewogICAgICAgIHN3YXAgKGFycltpXSwgYXJyW2xhcmdlXSk7CiAgICAgICAgTWF4SGVhcGlmeShhcnIsIGxhcmdlLCBoZWFwU2l6ZSk7CiAgICB9Cn0KCnZvaWQgQnVpbGRIZWFwKGludCBhcnJbXSwgaW50IG4pIHsKICAgIGludCBrID0gKG4vMiktMTsKICAgIGludCBqID0gMTsKICAgIGZvciAoaW50IGk9azsgaT49MDsgaS0tKSB7CiAgICAgICAgTWF4SGVhcGlmeShhcnIsIGksIG4pOwogICAgICAgIHByaW50ZigiQXJyYXkgYWZ0ZXIgJWQgTWF4LUhlYXBpZnlcbiIsIGorKyk7CiAgICAgICAgcHJpbnRBcnJheShhcnIsIG4pOwogICAgfQp9Cgp2b2lkIEhlYXBzb3J0IChpbnQgYXJyW10sIGludCBuKSB7CiAgICBCdWlsZEhlYXAoYXJyLCBuKTsKICAgIAogICAgZm9yIChpbnQgaT1uLTE7IGk+PTA7IGktLSkgewogICAgICAgIHN3YXAoYXJyWzBdLCBhcnJbaV0pOwogICAgICAgIG4tLTsKICAgICAgICBNYXhIZWFwaWZ5KGFyciwgMCwgbik7CiAgICB9Cn0KCmludCBtYWluKCkgewogICAgaW50IGFycltdID0gezgsIDMsIDksIDIsIDE2LCAxMCwgMTQsIDcsIDR9OwogICAgaW50IG4gPSBzaXplb2YoYXJyKS9zaXplb2YoYXJyWzBdKTsKICAgIAogICAgY291dDw8IkluaXRpYWwgQXJyYXk6Ijw8ZW5kbDsKICAgIHByaW50QXJyYXkoYXJyLCBuKTsKICAgIGNvdXQ8PGVuZGw7CiAgICAKICAgIEhlYXBzb3J0KGFyciwgbik7CiAgICAKICAgIGNvdXQ8PGVuZGw8PCJBcnJheSBhZnRlciBIZWFwc29ydDoiPDxlbmRsOwogICAgcHJpbnRBcnJheShhcnIsIG4pOwogICAgCiAgICByZXR1cm4gMDsKfQo=