(118). 31.2. HEAP SORT - anishsingh90/Data_Structure_And_Algorithm_In_Cpp_github.io GitHub Wiki

#include <bits/stdc++.h> using namespace std;

// Function to heapify a subtree rooted at node i void heapify(vector &a, int n, int i) { int maxIdx = i; int l = 2 * i + 1; int r = 2 * i + 2;

if (l < n && a[l] > a[maxIdx]) {
    maxIdx = l;
}
if (r < n && a[r] > a[maxIdx]) {
    maxIdx = r;
}

if (maxIdx != i) {
    swap(a[i], a[maxIdx]);

    heapify(a, n, maxIdx);
}

}

// Function to perform heap sort void heapsort(vector &a) { int n = a.size();

// Build max heap
for (int i = n / 2 - 1; i >= 0; i--) {
    heapify(a, n, i);
}

// Extract elements one by one from the heap
for (int i = n - 1; i > 0; i--) {
    swap(a[0], a[i]);

    // Call max heapify on the reduced heap
    heapify(a, i, 0);
}

}

int main() { int n; cout << "Enter the size of array: "; cin >> n;

vector<int> a(n);

for (int i = 0; i < n; i++) {
    cin >> a[i];
}

heapsort(a);

// Print the sorted array
for (int i = 0; i < n; i++) {
    cout << a[i] << " ";
}

return 0;

}

/* OUTPUT: Enter the size of array: 6 7 9 3 6 1 8 1 3 6 7 8 9 */

⚠️ **GitHub.com Fallback** ⚠️