[c++] 힙 정렬

12 Dec 2023

힙 정렬은 효율적인 정렬 알고리즘 중 하나로, 이진 힙 자료구조를 사용하여 정렬을 수행합니다. 힙 정렬은 평균 및 최악의 경우 모두 O(n log n)의 시간 복잡도를 가지며, 제자리 정렬(in-place sorting) 알고리즘 중 하나입니다.

이진 힙 자료구조

이진 힙은 완전 이진 트리(complete binary tree)를 기본으로 하는 자료구조로써, 최대 힙과 최소 힙 두 가지 종류가 있습니다. C++의 STL은 <algorithm> 헤더 파일에 make_heap, push_heap, pop_heap, sort_heap 등의 함수를 제공하여 힙 정렬을 구현할 수 있습니다.

C++ 코드 예시

다음은 C++를 사용하여 힙 정렬을 구현한 예시 코드입니다.

#include <iostream>
#include <algorithm>
#include <vector>

void heapSort(std::vector<int>& arr) {
    std::make_heap(arr.begin(), arr.end());
    std::sort_heap(arr.begin(), arr.end());
}

int main() {
    std::vector<int> arr = {12, 11, 13, 5, 6, 7};
    heapSort(arr);
    std::cout << "정렬된 배열: ";
    for (int num : arr) {
        std::cout << num << " ";
    }
    return 0;
}

이 코드에서 make_heap 함수를 사용하여 배열을 힙 구조로 만들고, sort_heap 함수를 통해 정렬을 수행합니다.

힙 정렬은 대규모 데이터에 대한 정렬이 필요한 경우에 유용하며, C++의 STL을 활용하여 간단하게 구현할 수 있습니다.

참고 자료

힙 정렬에 대해 더 자세히 알고 싶다면 위의 참고 자료를 확인해 보시기를 권장합니다.