Heap Sort Time : O(nlogn) Space : O(n) 123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051#include <vector>using namespace std;void push(vector<int>& heap, int v) { heap.push_back(v); int i = heap.size() - 1; while(i) { if(heap[i] < heap[i / 2]) swap(heap[i], heap[i / 2]); else break; i /= 2; }}int pop(vector<int>& heap) { int res = heap[0]; heap[0] = heap.back(); heap.pop_back(); int i = 0; while(true) { if(i * 2 + 1 < heap.size()) { int mi = min(heap[i * 2], heap[i * 2 + 1]); if(mi >= heap[i]) break; if(heap[i * 2] == mi) { swap(heap[i], heap[i * 2]); i = i * 2; } else { swap(heap[i], heap[i * 2 + 1]); i = i * 2 + 1; } } else if(i * 2 < heap.size()) { if(heap[i * 2] >= heap[i]) break; swap(heap[i], heap[i * 2]); i = i * 2; } else break; } return res;}vector<int> heapSort(vector<int> array) { vector<int> heap; for(auto& n : array) push(heap, n); int idx = 0; while(!heap.empty()) { array[idx++] = pop(heap); } return array;}