정렬 알고리즘 (Sorting Algorithms) - 힙 정렬 (Heap Sort)

힙 정렬 (Heap Sort)

힙 정렬은 힙 트리(Heap Tree) 자료구조를 기반으로 하는 효율적인 정렬 알고리즘입니다. 최대 힙(Max Heap) 또는 최소 힙(Min Heap)을 구성한 후, 요소를 제거하며 정렬을 수행합니다.

---

1. 작동 방식

1. 힙 생성 (Heapify):
   • 배열을 힙 트리로 변환합니다.
   • 최대 힙(Max Heap): 부모 노드가 자식 노드보다 크거나 같음.
   • 최소 힙(Min Heap): 부모 노드가 자식 노드보다 작거나 같음.
2. 정렬:
   • 최대 힙을 사용하여 가장 큰 값을 배열의 끝으로 보냅니다.
   • 배열의 크기를 줄이고 남은 요소로 힙을 재구성합니다.
   • 이 과정을 배열 크기가 1이 될 때까지 반복합니다.

---

2. 특징

• 시간 복잡도:
  • 힙 구성: O(n)
  • 정렬 과정: O(n log⁡ n)
  • 전체: O(n log⁡ n)
• 공간 복잡도:
  • 추가 메모리를 사용하지 않음: O(1)
• 비안정 정렬:
  • 동일한 값의 순서를 보장하지 않습니다.

---

3. 작동 과정

배열: [4, 10, 3, 5, 1]

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].

---

4. 장점과 단점

장점:

• 항상 O(n log n) 시간 복잡도를 가집니다.
• 추가 메모리를 사용하지 않아 공간 효율적입니다.

단점:

• 정렬이 안정적이지 않습니다.
• 구현이 상대적으로 복잡합니다.

반응형

---

5. Java 예제 코드

import java.util.Arrays;

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

        // Build max heap
        for (int i = n / 2 - 1; i >= 0; i--) {
            heapify(arr, n, i);
        }

        // Extract elements from heap
        for (int i = n - 1; i >= 0; i--) {
            // Move current root to the end
            int temp = arr[0];
            arr[0] = arr[i];
            arr[i] = temp;

            // Call heapify on reduced heap
            heapify(arr, i, 0);
        }
    }

    // Heapify a subtree rooted at index i
    void heapify(int[] arr, int n, int i) {
        int largest = i; // Initialize largest as root
        int left = 2 * i + 1; // Left child
        int right = 2 * i + 2; // Right child

        // If left child is larger than root
        if (left < n && arr[left] > arr[largest]) {
            largest = left;
        }

        // If right child is larger than largest so far
        if (right < n && arr[right] > arr[largest]) {
            largest = right;
        }

        // If largest is not root
        if (largest != i) {
            int swap = arr[i];
            arr[i] = arr[largest];
            arr[largest] = swap;

            // Recursively heapify the affected subtree
            heapify(arr, n, largest);
        }
    }

    public static void main(String[] args) {
        int[] arr = {4, 10, 3, 5, 1};
        System.out.println("Original Array: " + Arrays.toString(arr));

        HeapSort sorter = new HeapSort();
        sorter.heapSort(arr);

        System.out.println("Sorted Array: " + Arrays.toString(arr));
    }
}

---

6. Python 예제 코드

def heapify(arr, n, i):
    largest = i  # Initialize largest as root
    left = 2 * i + 1  # Left child
    right = 2 * i + 2  # Right child

    # If left child is larger than root
    if left < n and arr[left] > arr[largest]:
        largest = left

    # If right child is larger than largest so far
    if right < n and arr[right] > arr[largest]:
        largest = right

    # If largest is not root
    if largest != i:
        arr[i], arr[largest] = arr[largest], arr[i]  # Swap

        # Recursively heapify the affected subtree
        heapify(arr, n, largest)

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

    # Build max heap
    for i in range(n // 2 - 1, -1, -1):
        heapify(arr, n, i)

    # Extract elements from heap
    for i in range(n - 1, 0, -1):
        arr[i], arr[0] = arr[0], arr[i]  # Swap
        heapify(arr, i, 0)

# Example usage
if __name__ == "__main__":
    arr = [4, 10, 3, 5, 1]
    print("Original Array:", arr)

    heap_sort(arr)

    print("Sorted Array:", arr)

---

7. 활용 사례

• 대규모 데이터 정렬.
• 제한된 메모리 환경에서 사용.
• 안정 정렬이 필요하지 않은 경우.

힙 정렬은 항상 효율적인 성능을 보장하지만, 구현이 복잡하고 정렬 안정성을 제공하지 않으므로 특정 상황에서는 다른 알고리즘이 더 적합할 수 있습니다.