[Algorithm] 힙 정렬(Heap Sort)

⚪원리와 예시 코드

1. 원소들을 전부 힙에 삽입한다.
2. 힙의 루트에 있는 값은 남은 수들 중에서 최솟값(혹은 최댓값)을 가지므로 루트를 출력하고 힙에서 제거한다.
3. 힙이 빌 때까지 2의 과정을 반복한다.

선택 정렬(Selection Sort)과 거의 같은 알고리즘으로,
단지 가장 큰 원소를 뒤로 보내는 데에 단순히 매번 쭉 돌면서 알아내느냐 힙을 사용하여 알아내느냐가 유일한 차이점

힙정렬은 추가적인 메모리를 전혀 필요로 하지 않는다는 점과, 최악의 경우에 O(n²)의 성능을 내는 퀵정렬과 달리
항상 O(n log n) 정렬의 성능을 발휘하는 장점이 있다.
하지만 실제 코드를 짜서 비교를 해 보면 퀵정렬이 힙정렬보다 일반적인 경우에 빠르게 동작한다.

퀵정렬의 경우 피벗을 잡는 전략에 어느 정도의 휴리스틱이 들어가야 최악의 경우를 회피할 수 있으나 힙정렬은 휴리스틱이 필요없이 항상 일정한 성능을 보이는 장점이 있다.
즉 알고리즘에 꼼수를 쓰지 않고, 각종 하드웨어 가속도 전혀 고려하지 않고 알고리즘이 정의하는 최소한만 구현할 경우 힙정렬이 가장 안정적인 성능을 보인다

#include <iostream>
#include <vector>

// 최대 힙을 구성하는 함수
void Heapify(std::vector<int> &arr, int heapSize, int rootNodeIndex)
{
    int largestElementIndex = rootNodeIndex; // largest는 루트의 인덱스
    int leftChildIndex = 2 * rootNodeIndex + 1; // left는 왼쪽 자식의 인덱스
    int rightChildIndex = 2 * rootNodeIndex + 2; // right는 오른쪽 자식의 인덱스

    // 왼쪽 자식이 존재하고, 루트보다 크다면
    if (leftChildIndex < heapSize && arr[leftChildIndex] > arr[largestElementIndex])
        largestElementIndex = leftChildIndex;

    // 오른쪽 자식이 존재하고, 루트보다 크다면
    if (rightChildIndex < heapSize && arr[rightChildIndex] > arr[largestElementIndex])
        largestElementIndex = rightChildIndex;

    // largest가 루트가 아니라면 swap
    if (largestElementIndex != rootNodeIndex)
    {
        std::swap(arr[rootNodeIndex], arr[largestElementIndex]);
        Heapify(arr, heapSize, largestElementIndex); // 재귀적으로 힙 구성
    }
}

// 주어진 배열을 힙 정렬하는 함수
void HeapSort(std::vector<int> &arr)
{
    int arraySize = arr.size();

    // 먼저, 배열 arr을 최대 힙으로 만든다.
    // (arraySize/2-1)은 배열의 마지막 요소의 부모 노드의 인덱스
    for (int rootNodeIndex = arraySize / 2 - 1; rootNodeIndex >= 0; rootNodeIndex--)
        Heapify(arr, arraySize, rootNodeIndex);

    // 하나씩 요소를 추출하면서 힙을 재구성한다.
    for (int heapSize = arraySize - 1; heapSize >= 0; heapSize--)
    {
        std::swap(arr[0], arr[heapSize]); // 현재 루트(가장 큰 값)를 배열의 끝으로 이동 (이번 반복의 가장 큰 값 구한 것임)
        Heapify(arr, heapSize, 0); // 힙 재구성
    }
}

int main()
{
    std::vector<int> arr = {12, 11, 13, 5, 6, 7};
    HeapSort(arr); // 힙 정렬 실행
    for (int i = 0; i < arr.size(); i++)
        std::cout << arr[i] << " "; // 정렬된 결과 출력
    return 0;
}

정렬을 했을 때 중복된 값들의 순서가 변하는 불안정(Unstable) 정렬에 속한다

⚪시간 복잡도

O(n log n)