[알고리즘] 힙 정렬 (Heap Sort)

Heap Sort

개념

• 힙 자료구조를 활용하여 데이터를 정렬하는 정렬 알고리즘

• 최대 힙과 최소 힙 두 가지 종류가 있다.

• 평균 O(N logN) 시갖복잡도를 가진다.

정렬 과정

• 배열의 모든 원소를 이용하여 힙을 구축한다.

• 부모 노드가 자식 노드보다 크거나 같은 값을 가지도록 힙 속성을 유지한다.

• 배열의 중간부터 시작하여 힙 속성을 만족하도록 조정(Heapify)한다.

• 힙의 루트를 배열의 마지막 원소와 교환한다.

• 힙의 크기를 하나 줄이고, 남은 원소들로 다시 힙 속성을 유지하도록 조정한다.

• 힙의 크기가 1이 될 때까지 반복한다.

실습

실습 제목

void heapify(vector<int>& arr, int n, int i) {
    int largest = i; // 루트
    int left = 2 * i + 1; // 왼쪽 자식
    int right = 2 * i + 2; // 오른쪽 자식

    // 왼쪽 자식이 루트보다 큰 경우
    if (left < n && arr[left] > arr[largest])
        largest = left;

    // 오른쪽 자식이 현재 가장 큰 값보다 큰 경우
    if (right < n && arr[right] > arr[largest])
        largest = right;

    // 루트가 가장 큰 값이 아닌 경우
    if (largest != i) {
        swap(arr[i], arr[largest]);
        // 재귀적으로 힙 속성 유지
        heapify(arr, n, largest);
    }
}

void heapSort(vector<int>& arr) {
    int n = arr.size();

    // 최대 힙 만들기
    for (int i = n / 2 - 1; i >= 0; i--)
        heapify(arr, n, i);

    // 힙에서 원소를 하나씩 꺼내며 정렬
    for (int i = n - 1; i >= 0; i--) {
        swap(arr[0], arr[i]);
        heapify(arr, i, 0);
    }
}