자료구조 - 히프 정렬

[히프 정렬(Heap Sort)]

히프 정렬의 시간 복잡도는 O(n log n) 이며, 추가적인 메모리 공간을 필요로 하지 않기 때문에 제자리 정렬(in-place sorting) 알고리즘입니다.

 

 

히프 정렬 알고리즘

1.  리스트의 원소들을 모두 힙에 넣습니다.
2. 히프의 루트의 원소를 정렬 시킬 배열에 넣고 히프에서는 제거합니다.
3.  2의 과정을 n 번 진행합니다.

 

 

 

히프 정렬의 구현

#include <iostream>
#include <vector>

// 힙 정렬 함수
void heapSort(std::vector<int>& array) 
{
    int n = array.size();
    
    // 1. 주어진 배열을 최대 힙으로 변환
    for (int i = n / 2 - 1; i >= 0; --i) 
    {
        siftDown(array, n, i);
    }
    
    // 2. 정렬 과정
    for (int i = n - 1; i > 0; --i)
    {
        // 최대값(루트)을 배열의 끝과 교환
        std::swap(array[0], array[i]);
        
        // 힙 크기를 줄이고, 루트 노드에 대해 하향 조정 수행
        siftDown(array, i, 0);
    }
}

// 하향 조정 함수
void siftDown(std::vector<int>& array, int n, int i) 
{
    int largest = i;
    int left = 2 * i + 1;
    int right = 2 * i + 2;

    // 왼쪽 자식이 현재 노드보다 크면 largest 갱신
    if (left < n && array[left] > array[largest])
    {
        largest = left;
    }
    
    // 오른쪽 자식이 현재 노드보다 크면 largest 갱신
    if (right < n && array[right] > array[largest])
    {
        largest = right;
    }
    
    // 힙 속성이 유지되지 않으면 현재 노드와 largest 노드 교환
    if (largest != i) 
    {
        std::swap(array[i], array[largest]);
        // 하위 트리에 대해 재귀적으로 하향 조정 수행
        siftDown(array, n, largest);
    }
}

int main()
{
    std::vector<int> array = {3, 5, 1, 10, 2, 7, 6, 4};

    // 힙 정렬 수행
    heapSort(array);

    // 정렬된 배열 출력
    std::cout << "Sorted array: ";
    for (int val : array) 
    {
        std::cout << val << " ";
    }
    std::cout << std::endl;

    return 0;
}