# Untitled

unknown
c_cpp
a year ago
1.4 kB
1
Indexable
Never
```#include <bits/stdc++.h>
using namespace std;

int lChildIndx(int i) {
return 2*i + 1;
}

int rChildIndx(int i) {
return 2*i + 2;
}

int parentIndx(int i) {
return (i-1)/2;
}

// O(log n)
void maxHeapify(vector<int> &A, int indx, int size) {
while (indx < size) {
int lIndx = lChildIndx(indx);
int rIndx = rChildIndx(indx);
int largestIndx;

if (lIndx < size && A[lIndx] > A[indx])
largestIndx = lIndx;
else largestIndx = indx;

if (rIndx < size && A[rIndx] > A[largestIndx])
largestIndx = rIndx;

if (largestIndx != indx) {
swap(A[indx], A[largestIndx]);
indx = largestIndx;
} else {
break;
}
}
}

void buildMaxHeap(vector<int> &A, int size) {
for (int i = parentIndx(size - 1); i >= 0; i--) {
maxHeapify(A, i, size);
}
}

// O(nlog n)
void heapSort(vector<int> &A) {
buildMaxHeap(A, A.size()); // O(n) time
int size = A.size();
for (int i = size - 1; i > 0; i--) {
swap(A[0], A[size - 1]);
size--;
maxHeapify(A, 0, size); // O(log n) time. This is called n-1 time. So total = O(nlog n)
}

}

int main() {
vector<int> A = {6,9,4,15,7,2,11,10,13};
heapSort(A);

cout << "A : ";
for (auto ele : A)
cout << ele << ", ";

return 0;
}```