힙 heap

힙(Heap)은 완전 이진 트리 형태의 자료구조로, 우선순위 큐(Priority Queue)와 같은 응용에 자주 사용된다. 힙은 최대 힙(Max Heap)과 최소 힙(Min Heap)으로 나뉘며, 각각의 부모 노드는 자식 노드와 비교해 특정 조건을 만족해야 한다.

힙의 종류

1. 최대 힙 (Max Heap)
   • 부모 노드가 자식 노드보다 항상 크거나 같은 값을 가진다.
   • 트리의 루트 노드는 가장 큰 값을 가진다.
   • 최대값을 빠르게 찾을 수 있으며, 삽입과 삭제 연산에서 부모 노드와 자식 노드를 비교해 위치를 조정한다.
2. 최소 힙 (Min Heap)
   • 부모 노드가 자식 노드보다 항상 작거나 같은 값을 가진다.
   • 트리의 루트 노드는 가장 작은 값을 가진다.
   • 최소값을 빠르게 찾을 수 있으며, 삽입과 삭제 시 자식 노드와 비교해 위치를 조정한다.

힙의 특성

• 힙은 완전 이진 트리이므로 마지막 레벨을 제외한 모든 레벨이 채워져 있으며, 마지막 레벨은 왼쪽부터 차례로 채워진다.
• 힙은 삽입, 삭제와 같은 연산 시에 부모 노드와 자식 노드의 값을 비교해 트리의 구조를 유지하며 균형을 맞춘다.
• 최대값 또는 최소값을 빠르게 찾는 데 유리하며, 시간 복잡도는 삽입, 삭제, 탐색 모두 (O(\log n))이다.

힙의 주요 연산

1. 삽입(Insertion): 힙의 맨 끝에 새로운 노드를 삽입한 후, 부모 노드와 비교하면서 위로 올라가며 자리를 교환해 힙 속성을 유지한다.
2. 삭제(Deletion): 최대 힙에서는 최대값, 최소 힙에서는 최소값을 삭제한다. 루트 노드를 삭제한 후 마지막 노드를 루트로 옮기고, 자식 노드와 비교해 아래로 내려가며 힙 속성을 유지한다.

힙 구현 예시 (파이썬)

파이썬에서는 heapq 모듈을 사용해 최소 힙을 간단하게 구현할 수 있다. 최대 힙은 heapq 모듈을 응용하여 구현한다.

최소 힙 (Min Heap) 예시

import heapq  # heapq 모듈을 임포트

min_heap = []  # 최소 힙을 저장할 리스트 초기화

# 힙에 요소 추가 (push)
heapq.heappush(min_heap, 10)  # 10 삽입
heapq.heappush(min_heap, 5)   # 5 삽입
heapq.heappush(min_heap, 20)  # 20 삽입
heapq.heappush(min_heap, 1)   # 1 삽입

print("Min Heap:", min_heap)  # 최소 힙 상태 출력

# 힙에서 가장 작은 값 제거 (pop)
min_val = heapq.heappop(min_heap)
print("Removed Min Value:", min_val)  # 제거한 최소 값 출력
print("Min Heap after removal:", min_heap)  # 갱신된 최소 힙 출력

출력 결과:

Min Heap: [1, 5, 20, 10]
Removed Min Value: 1
Min Heap after removal: [5, 10, 20]

• 최소 힙에서는 heapq 모듈이 자동으로 리스트의 첫 번째 요소를 최소값으로 유지하도록 한다.
• 삽입(heappush)과 삭제(heappop) 연산을 통해 최소 힙의 성질을 유지한다.

최대 힙 (Max Heap) 예시

최대 힙은 heapq 모듈을 이용해 최소 힙을 응용하여 구현할 수 있다. 음수로 변환하여 삽입한 후, 값을 꺼낼 때 다시 음수를 취해 원래 값을 복원한다.

max_heap = []  # 최대 힙을 저장할 리스트 초기화

# 힙에 요소 추가 (push) - 음수로 변환하여 삽입
heapq.heappush(max_heap, -10)  # 10 삽입 (음수로 변환)
heapq.heappush(max_heap, -5)   # 5 삽입 (음수로 변환)
heapq.heappush(max_heap, -20)  # 20 삽입 (음수로 변환)
heapq.heappush(max_heap, -1)   # 1 삽입 (음수로 변환)

print("Max Heap:", [-x for x in max_heap])  # 최대 힙 상태 출력 (음수로 변환한 값을 다시 양수로)

# 힙에서 가장 큰 값 제거 (pop) - 꺼낸 후 양수로 변환
max_val = -heapq.heappop(max_heap)
print("Removed Max Value:", max_val)  # 제거한 최대 값 출력
print("Max Heap after removal:", [-x for x in max_heap])  # 갱신된 최대 힙 출력

출력 결과:

Max Heap: [20, 10, 5, 1]
Removed Max Value: 20
Max Heap after removal: [10, 1, 5]

힙의 활용 예시

1. 우선순위 큐(Priority Queue): 우선순위가 높은 요소를 먼저 처리해야 하는 경우, 힙을 사용해 효율적으로 구현할 수 있다.
2. 다익스트라 알고리즘: 그래프에서 최단 경로를 찾는 다익스트라 알고리즘에서 우선순위 큐로 최소 힙이 사용된다.
3. 힙 정렬(Heap Sort): 최대 힙이나 최소 힙을 이용해 데이터를 정렬하는 알고리즘이다.
4. 이벤트 처리 시스템: 이벤트 발생 시간이 빠른 순서대로 처리해야 할 경우, 힙을 사용해 이벤트를 관리할 수 있다.

힙은 이러한 다양한 상황에서 중요한 값(최대값 또는 최소값)을 빠르게 찾고 관리할 수 있도록 돕는 자료구조이다.