Heap 자료구조
Heap이란?
힙은 특정한 규칙을 가지는 트리로, 최댓값과 최솟값을 찾는 연산을 빠르게 하기 위해 고안된 완전이진트리를 기본으로 구현된 자료 구조이다.
Heap의 Parent Node의 Key 값과 Child Node Key 값 사이에는 대소 관계가 성립하게 되는데 정렬 방식에 따라 Min Heap과 Max Heap으로 나뉜다.
- 최소 힙: 부모 노드의 키값이 자식 노드의 키값보다 항상 작은 힙
- 최대 힙: 부모 노드의 키값이 자식 노드의 키값보다 항상 큰 힙
위의 사진에 보이는 트리 구조가 Heap의 구조인데, Heap의 특성 상 항상 Root Node에는 가장 작은 (혹은 큰) 우선순위를 가지는 값이 위치하게 된다.
Min Heap에서는 가장 작은 우선순위를 가지는 값이 Root로, Max Heap에서는 가장 큰 우선순위를 가지는 값이 Root로 오게됨.
Python을 활용한 알고리즘 풀이
Heap Module
Python에서는 내장 모듈인 heapq 모듈을 사용하여 쉽게 Heap 구조를 구현할 수 있다. 기본적인 방식은 최소 힙(Min Heap) 구조이다.
heapq 모듈은 Python의 List를 최소 힙(Min Heap)처럼 다룰 수 있도록 하기 때문에, 베이스가 되는 List가 필요하다. 빈 List를 생성하거나 원래 있는 List를 Heap 구조로 변경할 수 있다.
원소 추가 및 삭제
import heapq
# 빈 list 생성
heap = []
# 원소를 추가할 때, list도 계속해서 인자로 넘겨줘야함
heapq.heappush(heap, 50)
heapq.heappush(heap, 10)
heapq.heappush(heap, 20)
print(heap)
# [10, 50, 20]
# **heap[0] 즉, root node에는 항상 우선순위가 낮은 값이 위치하게 됨**
# 원소 삭제 또한 마찬가지로 list를 인자로 넘겨줌
****result = heapq.heappop(heap)
print(result)
print(heap)
# 10
# [20, 50]
# 가장 낮은 우선순위인 10이 반환되고 **그 다음 낮은 우선순위인 20이 root node에 위치**List를 Heap 구조로 변경하기
이미 생성해둔 리스트가 있다면 heapify 함수를 통해 즉각적으로 힙 자료형으로 변환할 수 있다.
heap2 = [50 ,10, 20]
heapq.heapify(heap2)
print(heap2)
# [10, 50, 20]어떤 문제에 활용하는 게 좋을까?
Heap 구조는 항상 최솟값이 0번째 index에 위치하기 때문에 최소값을 활용하는 문제나 약간의 변형을 통해 Max Heap을 사용하여 최대값을 활용하여 푸는 문제에 적합하다.
ex) 주어진 리스트의 모든 값이 T 이상이 될 때까지 최솟값 두 개를 합치기
Appendix
1. Max Heap 구현하기
Max Heap은 간단하게 Tuple을 사용해서 구현할 수 있다. 방법으로는 Heap에
(-value, value) 형태로 실제 Value에 음수를 붙혀 Key로 사용하게 되면 최대 우선순위를 갇는 값이 최소 우선순위로 바뀌게 된다.
heap_items = [1,3,5,7,9]
max_heap = []
for item in heap_items:
heapq.heappush(max_heap, (-item, item))
print(max_heap)
# [(-9, 9), (-7, 7), (-5, 5), (-3, 3), (-1, 1)]heapq.heappop() 함수를 사용하여 Root Node의 값을 제거/반환하게 되면 Tuple형태의 값이 나오게 되는데, 해당 값에서 1번째 index에 접근하면 실제 Max Heap 형태로 구현 가능하다.
2. queue.PriorityQueue() 와 Heapq의 차이
queue.PriorityQueue()는 heapq를 기반으로 만들어진 자료구조로 Thread Safe 한 대신 heapq보다 속도가 느리기 때문에 정확성과 시간 복잡도를 보는 알고리즘 코딩 테스트에서는 heapq를 사용하자
