힙 정렬 (Heap Sort) 총 정리 - 개념, 원리, 동작 예시, 시간 복잡도, C언어, Java, Python 예시코드, 주의점, 장단점

힙 정렬(Heap Sort) 총 정리

 

 

 

 

 

1. 힙 정렬이란?

힙 정렬은 힙(Heap) 자료구조를 기반으로 한 정렬 알고리즘으로, 완전 이진 트리를 활용합니다. 힙은 최대 힙(Max Heap) 또는 최소 힙(Min Heap)으로 구성되며, 힙 정렬은 최대 힙을 사용하여 배열을 정렬합니다.

---

 

 

2. 원리

1. 주어진 배열을 최대 힙(Max Heap)으로 변환합니다.
2. 힙의 루트(최댓값)를 배열의 끝으로 이동하고, 힙 크기를 줄인 뒤 나머지 힙을 다시 최대 힙으로 조정합니다.
3. 위 과정을 반복하여 정렬을 완료합니다.

---

 

 

3. 동작 예시 (구체적인 설명)

 

정렬할 배열: [4, 10, 3, 5, 1]

1. 최대 힙 생성:
   • 초기 배열: [4, 10, 3, 5, 1]
   • 최대 힙 변환: [10, 5, 3, 4, 1]
2. 루트 요소를 정렬:
   • 루트 10을 배열 끝으로 이동: [1, 5, 3, 4, 10]
   • 나머지 힙을 최대 힙으로 조정: [5, 4, 3, 1, 10]
3. 과정 반복:
   • 루트 5 이동: [1, 4, 3, 5, 10]
   • 최대 힙 조정: [4, 1, 3, 5, 10]
   • 루트 4 이동: [1, 3, 4, 5, 10]
   • 최대 힙 조정: [3, 1, 4, 5, 10]
4. 정렬 완료:
   • 최종 배열: [1, 3, 4, 5, 10]

반응형

---

 

 

4. 시간 복잡도

• 최선의 경우: O(n log n)
• 평균적인 경우: O(n log n)
• 최악의 경우: O(n log n)

---

 

 

5. 코드 예제

C 코드

#include <stdio.h>

void swap(int* a, int* b) {
    int temp = *a;
    *a = *b;
    *b = temp;
}

void heapify(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(int arr[], int n) {
    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() {
    int arr[] = {4, 10, 3, 5, 1};
    int n = sizeof(arr) / sizeof(arr[0]);

    heapSort(arr, n);

    for (int i = 0; i < n; i++)
        printf("%d ", arr[i]);
    return 0;
}

 

Java 코드

public class HeapSort {

    public void heapSort(int[] arr) {
        int n = arr.length;

        for (int i = n / 2 - 1; i >= 0; i--)
            heapify(arr, n, i);

        for (int i = n - 1; i > 0; i--) {
            int temp = arr[0];
            arr[0] = arr[i];
            arr[i] = temp;

            heapify(arr, i, 0);
        }
    }

    void heapify(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) {
            int swap = arr[i];
            arr[i] = arr[largest];
            arr[largest] = swap;

            heapify(arr, n, largest);
        }
    }

    public static void main(String[] args) {
        int[] arr = {4, 10, 3, 5, 1};
        HeapSort hs = new HeapSort();
        hs.heapSort(arr);

        for (int num : arr)
            System.out.print(num + " ");
    }
}

 

Python 코드

def heapify(arr, n, i):
    largest = i
    left = 2 * i + 1
    right = 2 * i + 2

    if left < n and arr[left] > arr[largest]:
        largest = left

    if right < n and arr[right] > arr[largest]:
        largest = right

    if largest != i:
        arr[i], arr[largest] = arr[largest], arr[i]
        heapify(arr, n, largest)

def heap_sort(arr):
    n = len(arr)

    for i in range(n // 2 - 1, -1, -1):
        heapify(arr, n, i)

    for i in range(n - 1, 0, -1):
        arr[i], arr[0] = arr[0], arr[i]
        heapify(arr, i, 0)

arr = [4, 10, 3, 5, 1]
heap_sort(arr)
print(arr)

---

 

 

6. 주의점

1. 힙 생성 과정에서의 시간 복잡도를 고려해야 합니다.
2. 배열을 최대 힙으로 변환할 때, 불필요한 연산을 최소화하도록 코드를 최적화해야 합니다.

---

 

 

7. 장단점

장점

• 시간 복잡도가 항상 O(n log n)으로 안정적임.
• 추가 메모리 사용이 적음 (인플레이스 정렬).

단점

• 구현이 상대적으로 복잡함.
• 데이터가 거의 정렬된 경우 다른 알고리즘에 비해 성능이 떨어질 수 있음.

 

 

8. 최적화된 힙 구현

아래 포스팅들에 최적화된 힙 구현 관련된 내용들을 정리했습니다. C언어로 구현한 예시코드들도 있으니까 꼭 보시길 추천드립니다.

2023.03.12 - [자료구조] - HEAP(1) - 힙 기본 구현 (C언어 구현, index 1부터 시작)

HEAP(1) - 힙 기본 구현 (C언어 구현, index 1부터 시작)

2023.03.12 - [자료구조] - HEAP (2) - 업그레이드 된 HEAP 힙 (특정원소 삭제, 업데이트 O(logN)만에 가능)

HEAP (2) - 업그레이드 된 HEAP 힙 (특정원소 삭제, 업데이트 O(logN)만에 가능)

 

 

함께 보면 좋은 글

코딩 테스트에 나오는 거의 모든 정렬 알고리즘들에 대해 비교했습니다. 언제 어떤 정렬 알고리즘을 쓰면 좋은지에 대해서도 작성했습니다. 아래 링크에 자세히 작성했습니다.

 

2025.01.03 - [알고리즘] - 정렬 알고리즘 총 정리 및 비교 - 각 알고리즘 별 장단점, 시간 복잡도, 공간 복잡도, 안정성, 주요 특징, 상황에 따른 선택 기준

정렬 알고리즘 총 정리 및 비교 - 각 알고리즘 별 장단점, 시간 복잡도, 공간 복잡도, 안정성, 주