[크래프톤 정글] 힙트리

힙 트리(Heap Tree)는 이진 트리의 일종으로, 최댓값 또는 최솟값을 효율적으로 관리하기 위해 설계된 자료 구조다. 힙 트리는 완전 이진 트리(Complete Binary Tree)의 형태를 가지며, 노드 간의 특정 순서 관계를 유지한다. 힙 트리는 주로 우선순위 큐(Priority Queue)를 구현하는 데 사용된다.

힙 트리의 종류

힙 트리는 크게 두 가지 유형으로 나뉜다:

1. 최대 힙(Max Heap): 부모 노드가 자식 노드보다 크거나 같은 값을 가진다. 따라서 루트 노드는 트리에서 가장 큰 값을 가진다.
2. 최소 힙(Min Heap): 부모 노드가 자식 노드보다 작거나 같은 값을 가진다. 따라서 루트 노드는 트리에서 가장 작은 값을 가진다.

힙 트리의 특성

1. 완전 이진 트리(Complete Binary Tree):

   • 힙 트리는 항상 완전 이진 트리의 형태를 유지한다. 완전 이진 트리는 모든 레벨이 완전히 채워져 있거나, 마지막 레벨만 왼쪽부터 차례로 채워져 있는 트리다. 이 특성 덕분에 힙은 배열로 쉽게 구현될 수 있다.

2. 힙 속성(Heap Property):

   • 최대 힙: 모든 부모 노드의 값은 자식 노드의 값보다 크거나 같아야 한다.
   • 최소 힙: 모든 부모 노드의 값은 자식 노드의 값보다 작거나 같아야 한다.

힙 트리의 배열 표현

힙 트리는 완전 이진 트리이기 때문에 배열로 쉽게 표현할 수 있다. 배열을 사용하여 힙을 표현할 때, 다음과 같은 인덱스 관계가 성립한다:

• 부모 노드: 배열 인덱스 i의 부모 노드는 (i - 1) // 2이다.
• 왼쪽 자식 노드: 배열 인덱스 i의 왼쪽 자식 노드는 2 * i + 1이다.
• 오른쪽 자식 노드: 배열 인덱스 i의 오른쪽 자식 노드는 2 * i + 2이다.

예를 들어, 힙을 배열로 나타내면 다음과 같다:

          10
         /  \
       7     5
      / \   / \
     3   2 1   4

이 힙은 배열 [10, 7, 5, 3, 2, 1, 4]로 표현된다.

힙의 주요 연산

1. 삽입(Insert):

   • 새로운 요소를 힙의 끝에 추가하고, 힙 속성을 유지하기 위해 상향 힙 정렬(Heapify Up) 또는 상향 조정(Bubble Up)을 수행한다.
   • 상향 힙 정렬은 새로운 요소가 부모보다 크거나 작지 않도록 트리의 루트까지 이동하며 비교하고 스왑하는 과정이다.
   • 시간 복잡도: O(log n)

2. 최대값 또는 최소값 제거(Extract-Max 또는 Extract-Min):

   • 루트 노드(최대값 또는 최소값)를 제거한 후, 힙의 마지막 노드를 루트로 이동시키고 하향 힙 정렬(Heapify Down) 또는 하향 조정(Bubble Down)을 수행한다.
   • 하향 힙 정렬은 루트 노드가 자식 노드보다 크거나 작지 않도록 트리의 아래로 이동하며 비교하고 스왑하는 과정이다.
   • 시간 복잡도: O(log n)

3. 힙 생성(Build Heap):

   • 주어진 배열을 힙으로 만드는 과정이다. 배열을 힙 구조로 변환하기 위해 하향 힙 정렬을 반복적으로 적용한다.
   • 이 과정은 기존 배열의 절반 노드부터 시작해 루트 노드까지 하향 힙 정렬을 수행함으로써 이루어진다.
   • 시간 복잡도: O(n)

4. 힙 정렬(Heap Sort):

   • 힙 정렬은 힙을 이용한 정렬 알고리즘으로, 최대힙을 사용하여 배열을 내림차순으로 정렬하거나 최소힙을 사용하여 오름차순으로 정렬할 수 있다.
   • 시간 복잡도: O(n log n)

힙 트리 연산의 예시

삽입 연산 예시 (최대 힙)

1. 초기 힙 상태:

          10
         /  \
        7    5
       / \  
      3   2 

   배열로 표현: [10, 7, 5, 3, 2]

2. 삽입: 8을 삽입.

   • 8을 배열의 끝에 추가: [10, 7, 5, 3, 2, 8]
   • 상향 조정 수행: 8은 부모 노드 5보다 크므로 스왑.
   • 결과:

            10
           /  \
          7    8
         / \   / 
        3   2 5

     배열로 표현: [10, 7, 8, 3, 2, 5]

최대값 제거 연산 예시 (최대 힙)

1. 초기 힙 상태:

          10
         /  \
        7    8
       / \   / 
      3   2 5

   배열로 표현: [10, 7, 8, 3, 2, 5]

2. 최대값 제거: 10을 제거.

   • 마지막 노드 5를 루트로 이동: [5, 7, 8, 3, 2]
   • 하향 조정 수행: 5는 자식 노드 8보다 작으므로 스왑.
   • 결과:

            8
           /  \
          7    5
         / \  
        3   2 

     배열로 표현: [8, 7, 5, 3, 2]

힙의 시간 복잡도

• 삽입(Insert): O(log n)

  • 삽입 후 트리의 높이에 비례하는 연산이 필요하기 때문에 O(log n)이다.

• 최대값 또는 최소값 제거(Extract-Max/Min): O(log n)

  • 최대값 또는 최소값 제거 후 하향 힙 정렬을 수행하는 과정이 트리의 높이에 비례하기 때문에 O(log n)이다.

• 힙 생성(Build Heap): O(n)

  • 주어진 배열을 힙으로 변환하는 과정에서 전체 노드에 대해 하향 힙 정렬을 수행하므로, 시간 복잡도는 O(n)이다.

• 힙 정렬(Heap Sort): O(n log n)

  • 힙 정렬은 힙에서 요소를 하나씩 추출하며 정렬하는 방식으로, n개의 요소에 대해 각각 O(log n) 시간의 정렬이 이루어지기 때문에 O(n log n)이다.

힙의 응용

1. 우선순위 큐(Priority Queue):

   • 힙은 우선순위 큐의 구현에 널리 사용된다. 최대힙은 최대 우선순위 요소를 빠르게 제거하는 데 사용되고, 최소힙은 최소 우선순위 요소를 빠르게 제거하는 데 사용된다.

2. 힙 정렬(Heap Sort):

   • 힙 정렬은 효율적인 비교 기반 정렬 알고리즘으로, 데이터의 정렬을 힙을 이용해 수행한다.

3. 알고리즘 최적화:

   • 다익스트라(Dijkstra)의 최단 경로 알고리즘이나 프림(Prim)의 최소 신장 트리 알고리즘에서 힙은 중요한 역할을 한다. 이러한 알고리즘에서는 우선순위 큐를 사용하여 효율적으로 최단 경로나 최소 비용 간선을 선택한다.

4. 동적 배열 합병(Merging K Sorted Lists):

   • 여러 개의 정렬된 배열을 합병하는 문제에서 힙을 사용하여 가장 작은 요소를 효율적으로 선택할 수 있다.

결론

힙 트리는 특정 규칙을 가진 완전 이진 트리로, 우선순위 큐와 같은 응용에서 매우 중요한 역할을 한다. 힙은 효율적인 삽입, 삭제, 정렬 연산을 제공하며, 그 시간 복잡도는 트리의 높이에 비례하여 O(log n)이다. 힙의 효율성 덕분에 다양한 알고리즘과 데이터 구조에서 널리 사용되며, 특히 대규모 데이터 처리나 실시간 우선순위 관리가 필요한 시스템에서 유용하게 활용된다.