Heap 힙

 

힙의 주요 특징

1. 완전 이진 트리(Complete Binary Tree):
   • 힙은 항상 완전 이진 트리의 구조를 가집니다.
   • 완전 이진 트리란 트리의 모든 레벨이 꽉 차 있으며, 마지막 레벨은 왼쪽에서 오른쪽으로 순서대로 채워져 있어야 합니다.
2. 부모-자식 간의 순서 관계:
   • 최대 힙 (Max-Heap): 부모 노드의 값이 항상 자식 노드의 값보다 큽니다.
     • 즉, 루트 노드가 트리에서 가장 큰 값을 가집니다.
   • 최소 힙 (Min-Heap): 부모 노드의 값이 항상 자식 노드의 값보다 작습니다.
     • 즉, 루트 노드가 트리에서 가장 작은 값을 가집니다.
3. 우선순위 큐:
   • 힙은 우선순위 큐를 구현하는 데 적합합니다.
   • 우선순위 큐에서 가장 우선순위가 높은 요소를 빠르게 찾아내고 제거해야 할 때, 힙은 O(log n) 시간 복잡도로 이를 처리할 수 있습니다.

힙의 주요 연산

1. 삽입 (Insert):
   • 새로운 요소를 힙에 삽입할 때는 완전 이진 트리 구조를 유지해야 합니다.
   • 우선 트리의 마지막 위치에 요소를 삽입한 후, 부모 노드와 비교하여 힙 속성을 유지하기 위해 상향식으로 교환 (heapify up) 과정을 거칩니다.
   • 시간 복잡도: O(log n)
2. 최대값/최소값 반환 (Peek):
   • 최대 힙에서는 루트 노드가 가장 큰 값이며, 최소 힙에서는 루트 노드가 가장 작은 값입니다.
   • 루트 노드를 바로 반환할 수 있습니다.
   • 시간 복잡도: O(1)
3. 삭제 (Delete):
   • 루트 노드를 삭제한 후, 트리의 마지막 노드를 루트로 이동시킵니다.
   • 그 후 하향식으로 교환 (heapify down) 과정을 거쳐 힙 속성을 다시 유지합니다.
   • 시간 복잡도: O(log n)
4. 힙 정렬 (Heap Sort):
   • 힙을 이용하여 정렬할 수 있습니다. 먼저 배열을 힙으로 구성한 후, 가장 큰 값을 차례로 제거하여 정렬된 배열을 얻습니다.
   • 시간 복잡도: O(n log n)

힙의 구조

• 완전 이진 트리의 구조로 인해 힙은 배열로 쉽게 구현할 수 있습니다. 배열의 인덱스에 따라 부모와 자식의 위치 관계를 정의할 수 있습니다.
  • 부모 노드 인덱스: i
  • 왼쪽 자식 인덱스: 2*i + 1
  • 오른쪽 자식 인덱스: 2*i + 2
  • 부모 노드 인덱스 (자식이 i일 때): (i-1) / 2

힙의 활용

1. 우선순위 큐: 우선순위를 기준으로 작업을 처리해야 할 때 사용. 힙은 가장 우선순위가 높은 요소를 O(log n) 시간에 찾고 제거할 수 있기 때문에 적합함.
2. 힙 정렬: O(n log n) 시간 복잡도를 갖는 정렬 알고리즘으로, 배열을 힙으로 구성하고 반복적으로 루트 요소를 제거하여 정렬할 수 있습니다.
3. 최소 신장 트리 (MST): 크루스칼 알고리즘이나 프림 알고리즘과 같은 최소 신장 트리 알고리즘에서 힙은 가장 작은 가중치를 가진 간선을 빠르게 찾는 데 사용됩니다.
4. 다익스트라 알고리즘: 그래프에서 최단 경로를 찾는 다익스트라 알고리즘에서도 우선순위 큐(힙)를 사용하여 최소 비용 경로를 효율적으로 계산합니다.