Heap Sort(힙 정렬)

 힙정렬에 대해서 힙 정렬은 완전 이진 트리인 힙을 이용한 선택 정렬의 일종입니다. 배열 요소들을 힙 구조로 재배열한 다음, 가장 큰 요소(또는 가장 작은 요소)를 배열의 끝부분으로 이동시키는 과정을 반복하여 전체 배열을 정렬합니다.

 현업에서는 어디에서 쓰일 수 있나? 힙 정렬은 데이터 스트림의 지속적인 입력과 동시에 최대값 또는 최소값을 빠르게 액세스해야 할 때 유용합니다. 따라서 실시간 처리 시스템, 운영 체제의 작업 스케줄링, 대용량 데이터의 배치 처리 등에 적합합니다.

힙 정렬 사이클

힙 정렬의 주요 사이클은 다음과 같이 진행됩니다:

1. 힙 구성: 입력 배열을 최대 힙(max-heap) 또는 최소 힙(min-heap) 구조로 변환합니다.
2. 요소 추출 및 재구성: 힙의 루트(최대값 또는 최소값)를 힙의 마지막 요소와 교환하고, 루트를 제외한 나머지 힙을 재구성합니다.
3. 반복: 위 과정을 배열이 정렬될 때까지 반복합니다.

힙 정렬 시간복잡도와 공간복잡도

• 시간 복잡도:
  • 모든 경우: 최선, 평균, 최악 모두 𝑂(𝑛log⁡𝑛)입니다.
• 공간 복잡도:
  • 메모리 사용량: 𝑂(1) - 힙 정렬은 주어진 배열 내에서 정렬을 수행하므로 추가적인 메모리를 필요로 하지 않습니다.
• 안정성:
  • 힙 정렬은 안정적인 정렬 방법이 아닙니다. 같은 값의 요소가 원래의 순서를 유지하지 않을 수 있습니다.

힙 정렬 예시 code (Java, Golang, Python)

Java 코드

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

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

        // One by one extract an element from heap
        for (int i = n - 1; i > 0; i--) {
            // Move current root to end
            int temp = arr[i];
            arr[i] = arr[0];
            arr[0] = temp;

            // call max heapify on the reduced heap
            heapify(arr, i, 0);
        }
    }

    // To heapify a subtree rooted with node i which is
    // an index in arr[]. n is size of heap
    void heapify(int arr[], int n, int i) {
        int largest = i; // Initialize largest as root
        int l = 2 * i + 1; // left = 2*i + 1
        int r = 2 * i + 2; // right = 2*i + 2

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

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

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

            // Recursively heapify the affected sub-tree
            heapify(arr, n, largest);
        }
    }
}

• 힙 구축: 배열의 절반에서 시작하여 최대 힙을 구성합니다. 이는 부모 노드가 자식 노드보다 크도록 배열을 재배열하는 과정입니다.
• 요소 추출 및 교환: 배열의 끝으로 최대값을 이동하고, 루트 노드(새로운 최대값)를 배열의 끝과 교환한 후, 남은 힙에 대해 다시 최대 힙을 유지합니다.
• 재귀적 힙화: 자식 노드 중 더 큰 값과 교환 후, 변경된 노드 위치에서 다시 힙 조건을 만족하도록 재귀적으로 힙화를 수행합니다.

Golang 코드

package main

import "fmt"

func heapify(arr []int, n, i int) {
    largest := i
    l := 2*i + 1
    r := 2*i + 2

    if l < n && arr[l] > arr[largest] {
        largest = l
    }
    if r < n && arr[r] > arr[largest] {
        largest = r
    }

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

func heapSort(arr []int) {
    n := len(arr)

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

    for i := n - 1; i > 0; i-- {
        arr[i], arr[0] = arr[0], arr[i]
        heapify(arr, i, 0)
    }
}

func main() {
    arr := []int{12, 11, 13, 5, 6, 7}
    heapSort(arr)
    fmt.Println("Sorted array is:", arr)
}

• 힙 구축: 배열을 최대 힙으로 구성합니다. 부모 노드는 자식 노드보다 항상 크거나 같아야 합니다.
• 힙에서 요소 추출: 최대 힙의 루트(최대값)를 배열의 마지막 요소와 교환하고, 힙 크기를 줄인 후에 힙을 재구성합니다.
• 효율적인 메모리 사용: Go의 슬라이스를 사용하여 추가 메모리 할당 없이 배열 내에서 작업을 수행합니다.

Python 코드

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

    if l < n and arr[l] > arr[largest]:
        largest = l
    if r < n and arr[r] > arr[largest]:
        largest = r
    if largest != i:
        arr[i], arr[largest] = arr[largest], arr[i]
        heapify(arr, n, largest)

def heapSort(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 = [12, 11, 13, 5, 6, 7]
heapSort(arr)
print("Sorted array is:", arr)

• 힙 구성: 배열을 반으로 나누고 거기서부터 힙 구조를 만들어갑니다.
• 최대 힙 유지: 배열의 가장 큰 값을 찾아 루트에 배치하고, 힙의 나머지 부분을 재정렬합니다.
• Python의 재귀적 구현: Python의 재귀 함수를 사용하여 간결하고 이해하기 쉽게 힙 정렬을 구현합니다.

힙 정렬의 장단점

장점:

• 시간 복잡도: 모든 경우에 𝑂(𝑛log⁡𝑛)을 제공합니다.
• 추가 메모리 사용이 적음: 인플레이스 정렬 방식으로 추가 배열이 필요 없습니다.
• 효율적인 최대/최소 값 추출: 힙의 특성상 최대값 또는 최소값을 즉각적으로 추출할 수 있습니다.

단점:

• 복잡한 구현: 단순 정렬 알고리즘에 비해 구현이 복잡합니다.
• 비안정 정렬: 동일한 요소의 상대적 순서가 유지되지 않을 수 있습니다.
• 예측 불가능한 성능: 특히 일부 특정 패턴의 데이터에 대해 예측하기 어려운 성능을 보일 수 있습니다.

추가 정보

힙 정렬은 모든 경우에 대해 𝑂(𝑛log⁡𝑛)의 시간 복잡도를 가집니다. 이는 힙 정렬의 기본 동작 방식 때문입니다. 힙 정렬은 두 주요 단계로 구성됩니다:

1. 힙 구축(Heap Construction): 이 단계에서는 입력 배열을 최대 힙이나 최소 힙의 형태로 조정합니다. 이 과정은 𝑂(𝑛)의 시간 복잡도를 가질 수 있습니다. 이는 빌드 힙 과정이 선형 시간에 수행될 수 있다는 사실 때문입니다. "빌드 힙" 단계만 본다면, 최선의 경우 𝑂(𝑛)이 맞습니다.
2. 힙에서 요소 추출(Sorting by Heap Extraction): 배열의 각 요소를 힙에서 제거하고, 배열의 끝부터 시작하여 적절한 위치에 다시 삽입합니다. 이 과정은 배열의 각 요소에 대해 𝑂(log⁡𝑛)의 시간이 소요되며, 이는 최대 또는 최소 요소를 제거할 때마다 힙의 재조정이 필요하기 때문입니다.

 따라서 전체 힙 정렬의 시간 복잡도는 이 두 단계의 조합으로, 최종적으로 𝑂(𝑛log⁡𝑛)이 됩니다. 힙 구성이 𝑂(𝑛)이 가능함에도 불구하고, 전체 정렬 과정에서 요소를 추출하고 힙을 재조정하는 과정이 반복되기 때문에, 이 부분이 전체 복잡도를 𝑂(𝑛log⁡𝑛)으로 만듭니다.

따라서, 힙 정렬은 최선, 평균, 최악의 경우 모두 𝑂(𝑛log⁡𝑛)의 시간 복잡도를 가집니다. 최선의 경우에 𝑂(𝑛)이라는 설명은 힙 구축 과정에만 해당되며, 전체 정렬 프로세스에 대한 복잡도는 아닙니다.