우선순위큐(priority queue, heap)
먼저 트리(tree) 자료구조에 대한 이해가 필요한데, 이 부분에 대한 설명은 나중에 작성하겠다.
힙(heap) 자료구조
힙(heap)은 최댓값 또는 최솟값을 찾는 연산을 빠르게 하기 위해 고안된 자료 구조로, 완전 이진트리를 기본 구조로 가진다.
- 힙 성질, heap property
- 부모 노드와 자식 노드 사이에는 키 값에 일정한 대소 관계가 존재한다.
- 최소 힙 :
- 부모 노드의 키 값이 자식 노드의 키 값보다 항상 작은 힙
- 최대 힙 :
- 부모 노드의 키 값이 자식 노드의 키 값보다 항상 큰 힙
이미지 출처 : https://javascript.plainenglish.io/real-world-uses-cases-for-heaps-e57edbeb7da3
힙 성질로 힙에서는 가장 높은 우선순위(min heap이라면 가장 작은 값)를 가지는 노드가 루트 노드에 위치하게 되고, 이를 이용해 우선순위 큐와 같은 자료 구조를 구현할 수 있다.
이때 키 값의 대소 관계는 부모/자식 간에만 성립한다. 하지만 구현의 편리성을 위해 __‘같은 level의 노드, 형제 노드 사이에서도 왼쪽의 노드가 오른쪽의 노드보다 커야한다’__는 조건을 정하기도 한다.
힙 성질을 만족시키는 힙 정렬 알고리즘
힙(heap)에서 원소를 추가하거나 삭제하면, 힙 성질을 만족시키기 위해 노드 값들의 변경이 필요하다.
추후 작성
파이썬(Python)에서의 힙 자료구조 구현
파이썬에서는 heapq라는 내장 모듈에 해당 알고리즘이 담겨있다.
PriorityQueue라는 모듈도 존재하는데, heapq 모듈이 성능 측면에서 훨씬 좋다.
https://docs.python.org/ko/3/library/heapq.html
위의 링크에서 모듈과 관련한 자세한 설명을 볼 수 있다.
여기서의 heapq는 최소 힙이다.
heapq method
- heapq.heappush(heap, item) : item을 heap에 추가
- heapq.heappop(heap) : heap에서 가장 작은 원소를 pop하고 return
- 비어 있는 경우 IndexError가 호출된다.
- heapq.heapify(x) : list x를 heap으로 변환 (O(N))
최대 힙 만들기
최대 힙을 구현하기 위해서는 넣어주는 변수에 -를 붙여 가장 작은 수를 가장 크게 만들면 된다.
즉 heap에 넣을 모든 원소에 -를 붙이게 되면 최대 힙을 구현가능하다.
힙에 원소를 추가할 때 (-item, item)의 튜플 형태로 넣어주면 튜플의 첫 번째 원소(-item)를 우선 순위로, 즉 가장 작은 값부터 정렬하여 힙을 구성하게 된다.
1
2
3
4
5
6
7
8
9
10
import heapq
heap_item = [2,4,6,8,10]
max_heap = []
for item in heap_item:
heapq.heappush(max_heap, (-item, item))
print(max_heap)
1
[(-10, 10), (-8, 8), (-4, 4), (-2, 2), (-6, 6)] #힙 정렬이 이루어짐
혹은 다음과 같은 방식으로도 가능하다.
1
2
3
4
5
6
7
8
9
10
11
import heapq
heap_item = [2,4,6,8,10]
tmp = []
for item in heap_item:
tmp.append((-item, item))
print(tmp)
heapq.heapify(tmp)
print(tmp)
1
2
[(-2, 2), (-4, 4), (-6, 6), (-8, 8), (-10, 10)]
[(-10, 10), (-8, 8), (-6, 6), (-2, 2), (-4, 4)] #힙 정렬이 이루어짐
heapify로 리스트를 heap으로 전환한 결과와, heappush로 리스트를 heap으로 전환한 결과가 다르다.
두 방식 다 힙 성질을 만족하므로, 어느 방식을 사용하든지 문제가 없다!
이 부분에 대한 내용은 아래 링크에 잘 정리되어 있어서 참고하면 좋을 것 같다.