정렬 3편 (힙(Heap)과 힙 정렬)

🚀 이 주제를 선택한 이유 & 학습 목표

선택 배경:
이전 글에서 분할 정복 기반의 병합 정렬과 퀵 정렬을 학습하며, 두 알고리즘이 가진 명확한 트레이드오프를 확인했습니다. 병합 정렬은 항상 O(n log n) 성능을 보장하지만 O(n)의 추가 공간이 필요했고, 퀵 정렬은 O(log n)의 공간만 사용하지만 최악의 경우 O(n²)의 성능 저하 위험이 있었습니다. 이에 "메모리도 적게 쓰면서, 최악의 경우에도 O(n log n)을 보장하는 정렬은 없을까?"라는 질문에 대한 답을 찾기 위해 힙 정렬을 학습합니다.

학습 목표:

1. '힙(Heap)' 자료구조의 정의(완전 이진 트리, 힙 속성)를 이해하고, 배열로 힙을 표현하는 원리를 설명할 수 있습니다.
2. 힙 정렬의 두 가지 핵심 단계인 '힙 구성(Build-Heap)'과 '추출 및 힙 복구(Heapify)' 과정을 코드 수준에서 이해합니다.
3. 병합, 퀵, 힙 정렬의 장단점을 종합적으로 비교하고, 각 알고리즘이 어떤 상황에 적합한지 판단할 수 있습니다.

📚 핵심 개념 및 원리

1. 핵심 자료구조: 힙 (Heap)

힙 정렬을 이해하기 위해서는 힙 자료구조에 대한 선행 학습이 필수적입니다. 힙은 '최댓값 또는 최솟값을 빠르게 찾기 위해' 고안된, 완전 이진 트리 기반의 자료구조입니다.

• 구조적 조건 (모양): 완전 이진 트리(Complete Binary Tree)여야 합니다. 즉, 마지막 레벨을 제외한 모든 레벨이 완전히 채워져 있으며, 마지막 레벨의 노드들은 왼쪽부터 채워져야 합니다.
• 값의 조건 (규칙): 부모-자식 간의 값에 대한 규칙(Heap Property)을 따릅니다.
  • 최대 힙 (Max Heap): 부모 노드의 값은 항상 자식 노드의 값보다 크거나 같습니다. 루트 노드는 항상 최댓값을 가집니다.
  • 최소 힙 (Min Heap): 부모 노드의 값은 항상 자식 노드의 값보다 작거나 같습니다. 루트 노드는 항상 최솟값을 가집니다.

배열을 이용한 힙 표현: 힙은 구조적으로 완전 이진 트리이므로, 인덱스 계산만으로 부모/자식 관계를 파악할 수 있어 1차원 배열로 효율적으로 구현할 수 있습니다.

• i의 부모 인덱스: (i - 1) / 2
• i의 왼쪽 자식 인덱스: 2 * i + 1
• i의 오른쪽 자식 인덱스: 2 * i + 2

2. 힙 정렬 (Heap Sort)

오름차순 정렬을 위해 최대 힙을 사용하며, 다음 두 단계로 동작합니다.

• 1단계: 힙 구성 (Build-Max-Heap): 정렬할 배열 전체를 최대 힙 구조로 만듭니다. 이 과정이 끝나면 배열의 첫 번째 요소(arr)는 전체 배열에서 가장 큰 값이 됩니다.

• 2단계: 추출 및 정렬:

  1. 힙의 루트(arr)를 힙의 가장 마지막 요소와 교환합니다.
  2. 가장 큰 값이 위치한 배열의 맨 끝은 이제 '정렬 완료' 구역으로 간주하고, 힙의 크기를 1 줄입니다.
  3. 새로운 루트로 인해 깨진 힙 속성을 복구하기 위해, 줄어든 힙에 대해 heapify를 수행합니다.
  4. 힙에 요소가 하나만 남을 때까지 1~3 과정을 반복합니다.

• 고려사항:

  • 보장된 성능과 효율적인 공간: 항상 O(n log n)의 시간 복잡도를 보장하면서도, 추가 메모리가 거의 필요 없는(O(1)) 큰 장점을 가집니다.
  • 캐시 비효율성: heapify 과정에서 트리의 서로 다른 레벨에 있는, 즉 메모리 상 멀리 떨어진 위치의 데이터와 잦은 교환이 발생할 수 있습니다. 이는 캐시 효율성을 떨어뜨려, 평균적인 실제 속도는 퀵 정렬보다 느린 경향이 있습니다.
  • 불안정 정렬 (Unstable Sort): 힙 구성 및 복구 과정에서 값들의 상대적 순서가 유지되지 않습니다.

• Java 코드 예시:

  public void heapSort(int arr[]) {
      int n = arr.length;
  
      // 1. Build Max Heap
      for (int i = n / 2 - 1; i >= 0; i--) {
          heapify(arr, n, i);
      }
  
      // 2. Extract elements from heap one by one
      for (int i = n - 1; i > 0; i--) {
          // Move current root to end
          int temp = arr;
          arr = arr[i];
          arr[i] = temp;
  
          // call max heapify on the reduced heap
          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);
      }
  }

💡 장점, 단점 및 비교

특징	병합 정렬	퀵 정렬	힙 정렬
시간 복잡도(평균)	O(n log n)	O(n log n)	O(n log n)
시간 복잡도(최악)	O(n log n)	O(n²)	O(n log n)
공간 복잡도	O(n)	O(log n)	O(1)
안정성 (Stability)	Stable	Unstable	Unstable
캐시 효율성	보통	좋음	나쁨

🤔 나의 이해와 생각 정리 (회고)

핵심 요약:
힙 정렬은 힙이라는 효율적인 자료구조를 활용하여, '가장 큰 값을 찾고 제자리에 놓는' 과정을 O(log n)으로 수행함으로써 전체 O(n log n)의 시간 복잡도를 제자리(in-place)에서 달성하는 알고리즘입니다.

새롭게 깨달은 점:

• 힙의 본질: 힙 정렬 학습의 가장 큰 장벽은 힙 자료구조 자체였습니다. 하지만 "물리적으로는 배열, 논리적으로는 트리"라는 개념을 받아들이고, 모든 관계를 '순수 인덱스 계산' 으로 처리한다는 것을 이해하자 heapify 함수의 코드가 명확하게 보이기 시작했습니다. 트리 구조를 구현하기 위해 복잡한 노드 객체나 포인터가 필요 없다는 점이 매우 인상적이었습니다.
• 하나의 배열, 두 개의 구역: "힙 크기를 줄인다"는 말이 실제로 배열 크기를 바꾸는 것이 아님을 이해하는 데 시간이 걸렸습니다. 정렬이 진행되면서 하나의 배열이 '힙 구역(앞부분)'과 '정렬 완료 구역(뒷부분)'이라는 두 개의 논리적 땅으로 나뉘는 것이었습니다. for문의 i는 두 구역의 경계선 역할을 하며, heapify 함수에 i 값을 힙 크기로 넘겨줌으로써 작업 범위를 동적으로 제한하는 방식은 매우 영리한 공간 활용법이었습니다.
• Build-Heap의 상향식 접근: 처음에는 heapify를 n-1부터 0까지 모두 해야 한다고 생각했지만, 자식이 없는 리프 노드는 이미 힙이라는 사실을 깨달았습니다. 마지막 부모 노드부터 시작하여 '아래에서 위로' 힙을 만들어가는(Bottom-up) 방식이 훨씬 효율적이라는 것을 알게 되었습니다.

더 궁금해진 점 / 의문점:
지금까지 배운 정렬들은 모두 '비교'에 기반하고 있어, 이론적으로 O(n log n)보다 빨라질 수 없다고 알려져 있습니다. 그렇다면 정수와 같이 특별한 속성을 가진 데이터에 대해서는 '비교'를 하지 않고도 더 빠르게 정렬할 방법은 없을까?

✨ 마무리하며

이 글을 통해 주요 비교 기반 정렬 알고리즘(O(n²), O(n log n))에 대한 학습을 마무리했습니다. 각 알고리즘의 동작 원리를 깊이 있게 탐구하며, 시간 복잡도, 공간 복잡도, 안정성, 캐시 효율성 등 다양한 관점에서 트레이드오프를 이해하는 시야를 갖게 되었습니다.