정렬: 힙 정렬

출처: 위키백과

 

힙 정렬이란?

힙 정렬(Heap Sort)은 완전 이진 트리인 힙(heap) 자료구조를 사용하여 배열을 정렬하는 효율적인 알고리즘입니다. 힙 정렬은 배열 내의 최대값(또는 최소값)을 찾아 맨 끝 요소와 교환하고, 힙의 크기를 줄여가며 이 과정을 반복함으로써 전체 배열을 정렬합니다.

 

힙 정렬의 작동 원리

힙 정렬은 먼저 입력 배열을 최대 힙(max heap)이나 최소 힙(min heap)으로 구성합니다. 이후, 힙의 루트(최대값 또는 최소값)를 배열의 마지막 요소와 교환하고, 힙의 크기를 하나 줄인 뒤, 다시 힙을 재구성합니다. 이 과정을 배열이 완전히 정렬될 때까지 반복합니다.

 

힙 정렬의 단계별 과정

1. 입력 배열을 최대 힙으로 구성합니다.
2. 힙의 루트(최대값)를 배열의 마지막 요소와 교환합니다.
3. 힙의 크기를 하나 줄이고, 힙을 재구성합니다.
4. 위의 과정을 배열이 정렬될 때까지 반복합니다.

힙 정렬의 복잡도

시간 복잡도: 모든 경우에 O(n log n)입니다.
공간 복잡도: O(1)로, 추가적인 메모리 공간이 필요 없습니다.

---

Pseudocode

function heapSort(arr) {
  n = length(arr)

  // Build a max heap.
  for i = n / 2 - 1 down to 0
    heapify(arr, n, i)

  // One by one extract elements from heap
  for i = n - 1 down to 0
    // Move current root to end
    swap arr[0] with arr[i]
    // 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[].
function 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 left child is larger than root
  if l < n and arr[l] > arr[largest]
    largest = l

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

  // If largest is not root
  if largest != i
    swap arr[i] with arr[largest]
    // Recursively heapify the affected sub-tree
    heapify(arr, n, largest)
}

 

실제 예시로 이해하기

예를 들어, [12, 11, 13, 5, 6, 7] 배열을 오름차순으로 정렬한다고 해봅시다.

1. 배열을 최대 힙으로 구성합니다.
2. 힙의 루트(현재 최대값)와 배열의 마지막 요소를 교환합니다.
3. 힙의 크기를 하나 줄이고, 힙을 재구성합니다.
4. 모든 요소가 정렬될 때까지 위의 과정을 반복합니다.

결과적으로, 오름차순으로 정렬된 배열 [5, 6, 7, 11, 12, 13]을 얻을 수 있습니다.

힙 정렬은 효율적인 시간 복잡도와 추가 메모리를 요구하지 않는 공간 복잡도로 인해, 대용량 데이터 처리에 적합한 정렬 방법 중 하나입니다.