힙 정렬 (Heap Sort) (C++)

힙 정렬 (Heap Sort)

힙 정렬은 힙(Heap) 자료구조를 이용한 정렬 알고리즘으로, 완전 이진 트리의 특성을 활용하여 데이터를 정렬. 힙 정렬은 선택 정렬의 확장으로 볼 수 있으며, 데이터를 효율적으로 정렬하기 위해 최대 힙(Max Heap) 또는 최소 힙(Min Heap)을 사용.

---

동작 원리

1. 힙 생성 (Heapify):
   • 주어진 배열을 최대 힙(부모가 자식보다 크거나 같음) 또는 최소 힙(부모가 자식보다 작거나 같음)으로 변환.
2. 정렬:
   • 힙의 루트(최댓값 또는 최솟값)를 배열의 끝으로 이동하고, 힙 크기를 줄인다.
   • 줄어든 힙에 대해 다시 힙 구조를 유지하도록 정렬(Heapify).
   • 이 과정을 힙 크기가 1이 될 때까지 반복.

---

특징

• 시간 복잡도:
  • 최선/평균/최악: O(nlog⁡n)
  • 힙 구성: O(n), 삭제 및 정렬: O(nlog⁡n)
• 공간 복잡도: O(1) (제자리 정렬, 추가 메모리 필요 없음)
• 비안정적 정렬: 동일한 값의 순서가 바뀔 수 있음.
• 효율성: 대규모 데이터 정렬에 적합하며, 메모리 사용량이 적음.

---

예제 코드 (C++)

오름차순 힙 정렬

#include <iostream>
#include <vector>
using namespace std;

// 힙 구성 함수: 부모와 자식 간의 힙 조건을 유지
void heapify(vector<int>& arr, int n, int i) {
    int largest = i;           // 현재 루트
    int left = 2 * i + 1;      // 왼쪽 자식
    int right = 2 * i + 2;     // 오른쪽 자식

    // 왼쪽 자식이 더 크면 largest 업데이트
    if (left < n && arr[left] > arr[largest]) {
        largest = left;
    }

    // 오른쪽 자식이 더 크면 largest 업데이트
    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);
    }
}

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

    heapSort(arr);

    cout << "정렬 후 배열: ";
    for (int num : arr) cout << num << " ";
    cout << endl;

    return 0;
}

 

---

코드 설명

1. heapify 함수:
   • 현재 노드와 자식 노드 간의 관계를 확인하고, 최대 힙 조건을 유지.
   • 부모 노드가 자식보다 작으면 교환하고, 변경된 서브트리에 대해 재귀적으로 호출.
2. heapSort 함수:
   • 배열을 최대 힙으로 변환.
   • 힙의 루트(최댓값)를 배열의 끝으로 이동한 뒤, 힙 크기를 줄이고 다시 정렬.
3. 시간 복잡도 분석:
   • 힙 구성: O(n)
   • 요소를 하나씩 정렬하며 힙 조건 유지: O(nlog⁡n)

---

예제 동작 과정

입력 배열: [12, 11, 13, 5, 6, 7]

1. 최대 힙 구성:
   • 초기 배열: [12, 11, 13, 5, 6, 7]
   • 13을 루트로 하는 최대 힙 → [13, 11, 12, 5, 6, 7]
2. 정렬 과정:
   • 루트(13)를 마지막 요소와 교환 → [7, 11, 12, 5, 6, 13]
   • 힙 크기를 줄이고 다시 정렬 → [12, 11, 7, 5, 6, 13]
   • 반복하여 최종 정렬된 배열 생성.
3. 최종 정렬된 배열: [5, 6, 7, 11, 12, 13]

---

장점과 단점

장점

• 추가 메모리가 필요하지 않아 공간 효율적.
• 항상 O(nlog⁡n)의 시간 복잡도를 가짐.

단점

• 비안정적 정렬: 데이터의 순서가 유지되지 않음.
• 구현이 다소 복잡.

---

활용 사례

• 제한된 메모리 환경에서 대규모 데이터 정렬.
• 데이터가 랜덤하게 섞여 있고, 안정성이 필요 없는 경우.