Heap Sort

 

 

 

#include <bits/stdc++.h>



template<typename T>
void HeapSort(std::vector<T> & arr) {
    // maxHeap;
    std::priority_queue<T> pq;

    for (int i = 0; i < arr.size(); ++i){
        pq.push(arr[i]);
    }

    for (int i = arr.size() - 1; i >= 0; --i){
        int largest = pq.top(); pq.pop();
        arr[i] = largest;
    }
}



template<typename T>
void printArr(std::vector<T> arr){
    for (auto ele : arr) {
        std::cout << ele << " ";
    }
    std::cout << "\n";
}



int main(int argc, char** argv) {

    std::ios_base::sync_with_stdio(false);
    std::cin.tie(nullptr);

    std::vector<int> arr = {3, 5, 7, 9, 4, 2};
    std::cout << "before : ";
    printArr(arr);
    
    HeapSort(arr);

    std::cout << "after  : ";
    printArr(arr);
	return 0;
}

 

 

정리

시간복잡도 O(N) + O(NlogN) = O(NlogN)

공간복잡도 O(1) ---> heapify를 사용하는 경우