[자료구조] 힙(Heap)

힙(Heap)은 완전 이진 트리(Complete Binary Tree) 형태를 가지는 자료구조로, 각 노드의 값이 특정한 조건을 만족하도록 정렬된 트리입니다. 힙은 주로 우선순위 큐(Priority Queue)를 구현할 때 사용되며, 그 특성 때문에 빠른 삽입과 삭제 연산이 가능합니다.

힙의 특성

힙은 다음 두 가지 특성을 가집니다.

1. 완전 이진 트리(Complete Binary Tree):
   • 트리가 완전히 채워져 있으며, 마지막 레벨을 제외한 모든 레벨이 꽉 차 있습니다.
   • 마지막 레벨에서는 노드들이 왼쪽부터 오른쪽으로 채워져 있습니다.
2. 힙 특성(Heap Property):
   • 최대 힙(Max Heap): 부모 노드의 값이 자식 노드의 값보다 크거나 같아야 합니다. 즉, 트리의 루트(root) 노드는 항상 최대값입니다.
   • 최소 힙(Min Heap): 부모 노드의 값이 자식 노드의 값보다 작거나 같아야 합니다. 즉, 트리의 루트(root) 노드는 항상 최소값입니다.

힙의 주요 연산

힙에서 중요한 연산으로는 삽입과 삭제가 있습니다.

1. 삽입(Insert):
   • 새로운 요소를 힙의 가장 마지막 위치에 삽입합니다.
   • 힙 특성을 유지하기 위해 삽입된 요소를 부모 노드와 비교하며 올려보냅니다(Heapify Up).
2. 삭제(Delete):
   • 최상위 노드(루트)를 제거합니다.
   • 힙의 마지막 요소를 루트로 올리고, 힙 특성을 유지하기 위해 이 요소를 자식 노드들과 비교하며 내려보냅니다(Heapify Down).

힙의 시간 복잡도

• 삽입과 삭제 연산의 시간 복잡도는 O(log n) 입니다. 힙은 트리의 높이가 log n에 비례하므로, 삽입과 삭제 연산 시 힙을 정렬하는 데 필요한 비교 연산의 횟수도 log n에 비례합니다.

---

최소 힙 (Min Heap) 예시 코드

import heapq

# 최소 힙 예시
min_heap = []

# 힙에 값 추가
heapq.heappush(min_heap, 5)
heapq.heappush(min_heap, 1)
heapq.heappush(min_heap, 3)

# 힙의 상태 출력
print("Min Heap:", min_heap)  # [1, 5, 3]

# 최솟값을 꺼내기
min_val = heapq.heappop(min_heap)
print("Popped Min Value:", min_val)  # 1
print("Min Heap after pop:", min_heap)  # [3, 5]

 

최대 힙 (Max Heap) 예시 코드

import heapq

# 최대 힙 예시
max_heap = []

# 힙에 값 추가 (부호를 반대로 해서 추가)
heapq.heappush(max_heap, -5)
heapq.heappush(max_heap, -1)
heapq.heappush(max_heap, -3)

# 힙의 상태 출력 (부호를 다시 돌려서 출력)
print("Max Heap:", [-x for x in max_heap])  # [5, 1, 3]

# 최댓값을 꺼내기 (부호를 다시 돌려서 꺼내기)
max_val = -heapq.heappop(max_heap)
print("Popped Max Value:", max_val)  # 5
print("Max Heap after pop:", [-x for x in max_heap])  # [3, 1]

 

• 최소 힙: heapq 모듈을 사용하여 기본적으로 최소 힙을 구현할 수 있습니다. 값이 자동으로 정렬되며, heappop을 통해 최솟값을 꺼낼 수 있습니다.
• 최대 힙: 최소 힙에서 값을 부호 반대로 삽입하고 꺼낼 때도 부호를 반대로 하여 최대 힙을 구현할 수 있습니다. 이렇게 하면 heapq 모듈을 그대로 사용하면서도 최대 힙처럼 동작하게 만들 수 있습니다.

---

주요 메서드 요약

• heappush(heap, item): 힙에 item을 추가하면서 힙 특성을 유지합니다.
• heappop(heap): 힙의 최상위 요소를 제거하고 반환합니다.
• heappushpop(heap, item): item을 힙에 추가한 후, 최상위 요소를 제거하고 반환합니다.
• heapreplace(heap, item): 최상위 요소를 제거한 후, 새로운 item을 삽입합니다.
• heapify(heap): 기존 리스트를 힙으로 변환합니다.