※ Heap 이란?
Complete Binary Tree(완전 이진 트리)로 구성된 특수한 자료구조이다. Heap은 Priority Queue를 구현하기 위해 사용된다.
Heap 종류
- Max Heap(최대 힙)
- 부모 노드의 값이 자식 노드의 값보다 크거나 같은 Tree
- Min Heap(최소 힙)
- 부모 노드의 값이 자식 노드의 값보다 작거나 같은 Tree
- Min - Max Heap
- Min Heap과 Max Heap을 동시에 만족하는 자료구조
- 짝수 Level은 Min Heap을 따르고, 홀수 Level은 Max Heap을 따른다.
- Root Node는 최솟값을 제공하고, 그 자식 노드들은 최대값을 제공한다.
- Min Max Heap을 통해 최상위 레벨에서 최소값과 최대값을 빠르게 추출할 수 있는 장점이 있다.
- Sibling 간의 대소 관계는 정해지지 않는다.
Heap 동작
- Insert : Tree의 마지막 위치에 값을 추가한 후 Parent Node와 비교하여 Sift - Up을 수행한다
- Remove : Root Node를 삭제 후, 마지막 Leaf Node를 Root로 이동하여 Sift - Down을 수행한다.
1. Heap Method 사용 방법
Python의 Heap 라이브러리인 heapq는 Min Heap 사용하기 더 용이하기 때문에 Min Heap 기준으로 설명드리겠습니다.
heapify(heap:list)
List를 Min Heap으로 바꿔줍니다. Heap는 완전 이진 트리의 특수한 구조이란것을 앞서 설명드렸지만 heapify를 사용하면 완전 이진 트리의 Node를 연결하는 것이 아닌 List를 변형해서 완전 이진트리로 바꿔줍니다.(Index를 통한 접근)
import heapq
pq = [5, 3, 9, 4, 1, 2, 6]
heapq.heapify(pq)
print(pq)[1, 3, 2, 4, 5, 9, 6]
heapify의 결과로 만들어진 Min Heap Graph입니다.
완전 이진 트리의 성질에 따라 부모 Node의 Index 가 i일 때, Left Child는 $2*i + 1$, Right Child는 $2*i + 2$입니다.
따라서, $i=1$일 때 Left Child 4는 $i=3$, Right Child 5는 $i=4$임을 확인할 수 있습니다.
heappop(heap:list)
Heap의 Root를 제거하고 그 값을 Return 합니다.
import heapq
pq = [5, 3, 9, 4, 1, 2, 6]
heapq.heapify(pq)
print(heapq.heappop(pq))
print(pq)1
[2, 3, 6, 4, 5, 9]
heappush(heap:list, item=)
Heap에 Item을 추가합니다.
import heapq
pq = [5, 3, 9, 4, 1, 2, 6]
heapq.heapify(pq)
heapq.heappush(pq, 10)
print(pq)[1, 3, 2, 4, 5, 9, 6, 10]
heappushpop(heap:list, item=)
Heap에 Item을 먼저 추가한 후, Root를 제거하고 반환하는 함수이다.
heappush() 후에 heappop()을 한 것과 같지만, 한 번의 연산으로 처리되므로 성능이 더 좋다($O(logn)$)
import heapq
pq = [5, 3, 9, 4, 1, 2, 6]
heapq.heapify(pq)
heapq.heappushpop(pq, 7)
print(pq)
1
[2, 3, 6, 4, 5, 9, 7]
추가할 Item인 7를 추가하고, Root인 1을 제거한 후 Min Heap에 맞게 다시 조정합니다.
heapreplace(heap:list, item=)
Heap의 Root를 제거하고, Item을 추가한다.
heappop() 후 heappush()를 한 것과 같은 효과지만, 한 번의 연산으로 처리되어 더 성능이 좋다($O(logn)$)
import heapq
pq = [5, 3, 9, 4, 1, 2, 6]
heapq.heapify(pq)
print(heapq.heapreplace(pq, 7))
print(pq)1
[2, 3, 4, 4, 5, 9, 6]
heappushpop()과 heapreplace()는 동작과정이 유사하기 때문에 주의할 필요가 있다.
- heappushpop() : 먼저 Item을 추가 후 root를 제거하기 때문에 새로운 값이 기존 최솟값보다 작다면 효율적
- heapreplace() : 먼저 root를 제거하고 Item을 추가하기 때문에 새로운 값이 기존 최솟값보다 크다면 더 효율적
nlargest(n=, heap:list, key=), nsmallest(n=, heap:list, key=)
Heap에서 n개의 큰(작은) Element를 찾아서 반환한다.
import heapq
pq = [5, 3, 9, 4, 1, 2, 6]
heapq.heapify(pq)
print(heapq.nlargest(3, pq))
print(heapq.nsmallest(3, pq))[9, 6, 5]
[1, 2, 3]
key를 이용해 Key에 해당하는 기준에 따라 nlargest 또는 nsmallest를 구할 수 있다.
아래 Code는 list의 2번째 원소를 기준으로 2개의 큰 Element를 구하는 Code이다.
import heapq
students = [("철수", 85), ("영희", 95), ("민지", 70), ("민규", 90)]
print(heapq.nlargest(2, students, key=lambda x: x[1]))[('Bob', 95), ('David', 90)]
merge(*iterable=, key=, reverse=)
정렬된 여러 개의 Iterable을 하나의 정렬된 Iterable로 병합하는 Method이다.
Heap을 사용하여 정렬된 상태를 유지하면서 병합한다. 이 과정에서 모든 Element를 한꺼번에 정렬하는 것이 아니라 필요할 때마다 최소값을 Return하는 Iterator를 생성하여 병합하게 된다.
import heapq
li1 = [1, 4, 7]
li2 = [2, 5, 8]
li3 = [3, 6, 9]
res = heapq.merge(li1, li2, li3)
print(list(res))[1, 2, 3, 4, 5, 6, 7, 8, 9]
오름차순으로 정렬된 3개의 List를 정렬된 상태를 유지하면서 병합하게됩니다.
import heapq
li1 = [9, 6, 3]
li2 = [8, 5, 2]
li3 = [7, 4, 1]
res = heapq.merge(li1, li2, li3, reverse=True)
print(list(res))[9, 8, 7, 6, 5, 4, 3, 2, 1]
내림차순으로 정렬하기 위해서는 reverse를 사용하는데 이 때 각 List들도 내림차순으로 정렬되어있어야 올바른 결과를 얻을 수 있습니다.
import heapq
li1 = [(1, "apple"), (4, "banana")]
li2 = [(2, "cherry"), (3, "watermelon")]
res = heapq.merge(li1, li2, key=lambda x: x[0])
print(list(res))[(1, 'apple'), (2, 'cherry'), (3, 'watermelon'), (4, 'banana')]
Key를 통해 특정 Element를 기준으로 병합할 수 있습니다.
_heapify_max(heap:list)
heapq 라이브러리는 Max Heap를 생성하는 _heapify_max Method를 지원합니다. 하지만 heapq의 나머지 Method들은 Min Heap 기준으로 구현이 되어있어 올바른 결과를 얻지 못합니다.
import heapq
pq = [5, 3, 9, 4, 1, 2, 6]
heapq._heapify_max(pq)
print(pq)
print(heapq.heappop(pq))
heapq.heappush(pq, 9)
print(pq)[9, 4, 6, 3, 1, 2, 5]
9
[4, 1, 6, 3, 5, 2, 9]
heappop()은 올바르게 동작하지만, heappush()는 Min Heap의 동작을 수행함을 확인할 수 있습니다. 따라서 _heapify_max()는 Heap에 새로운 Element를 추가하지 않고 Pop만을 하는 문제라면 사용할 수 있습니다. 하지만 Max Heap에 추가, 제거 등을 하면서 Max Heap을 유지하기 위해서는 다른 방법을 사용해야 합니다.
그 방법은 Heap으로 만들기 위한 데이터에 -1을 곱해주어 Max 값이 Min값을 가지게 하고 Min Heap을 만드는 것입니다.
import heapq
pq = [5, 3, 9, 4, 1, 2, 6]
pq = [-1 * x for x in pq]
heapq.heapify(pq)
print(pq)
print(heapq.heappop(pq))
heapq.heappush(pq, -9)
print(pq)[-9, -4, -6, -3, -1, -2, -5]
-9
[-9, -4, -6, -3, -1, -2, -5]
위와 같은 과정을 통해 Max Heap을 사용할 수 있게 됩니다.
2. Prioirty Queue(우선순위 큐) 개념
Priority Queue는 Queue의 일종으로, 각 Element가 우선순위를 가지고 있으며, Queue에서 원소를 꺼낼 때 우선순위가 가장 높은 원소부터 꺼내는 자료구조이다.
Priority Queue 특징
- 내부적으로 Heap을 사용하여 구현한다.
- 우선순위가 높은 원소가 먼저 나온다.
- Min Heap : 값이 작은 원소가 우선순위가 높다.
- Max Heap : 값이 큰 원소가 우선순위가 높다.
import heapq
pq = []
heapq.heapify(pq)
heapq.heappush(pq, (2, "apple"))
heapq.heappush(pq, (1, "banana"))
heapq.heappush(pq, (3, "cherry"))
# 가장 우선순위가 높은 원소 꺼내기 (우선순위가 낮은 숫자부터 꺼내짐)
print(heapq.heappop(pq))
print(heapq.heappop(pq))
print(heapq.heappop(pq))(1, 'banana')
(2, 'apple')
(3, 'cherry')
(우선 순위, 값)을 삽입 한 후 heappop()을 사용하여 우선순위가 높은 Element(값이 작은)를 꺼낼 수 있다.
여기서도 heapq는 Min Heap을 사용하므로, 내림차순 Priority Queue를 사용하기 위해서는 우선 순위 * -1 을 통해 사용할 수 있다.
Priority Queue 응용
- Process Scheduling : 여러 작업 중 우선 순위에 따라 처리
- Dijkstra Algorithm : Graph에서 최단거리 찾기
- 등등 여러 알고리즘에서 Priority Queue를 사용합니다.
3. Prioirty Queue 예제
Priority Queue 사용하는 예제입니다(백준 2075번 - 2075번: N번째 큰 수)
문제
N×N의 표에 수 $N^2$ 개 채워져 있다. 채워진 수에는 한 가지 특징이 있는데, 모든 수는 자신의 한 칸 위에 있는 수보다 크다는 것이다. N=5일 때의 예를 보자.
이러한 표가 주어졌을 때, N번째 큰 수를 찾는 프로그램을 작성하시오. 표에 채워진 수는 모두 다르다.
Input
첫째 줄에 N(1 ≤ N ≤ 1,500)이 주어진다. 다음 N개의 줄에는 각 줄마다 N개의 수가 주어진다. 표에 적힌 수는 -10억보다 크거나 같고, 10억보다 작거나 같은 정수이다
Output
첫째 줄에 N번째 큰 수를 출력한다.
풀이
Priority Queue에 있는 원소 중 최소값과 현재 값을 비교하여 현재 값이 더 크다면 Priority Queue의 최소값을 제거하고 현재 값을 추가합니다.
이로써 Matrix를 모두 확인하면 Priority Queue에는 Matrix에서 1 ~ N 번째까지 큰 수를 가지고 있게 됩니다.
import heapq
N = int(input())
pq = []
heapq.heapify(pq)
for i in range(N):
row = list(map(int, input().split()))
for j in range(N):
# Priority Queue에 N개가 다 차지않았으면 push
if len(pq) < N:
heapq.heappush(pq, row[j])
# Priority Queue에 N개가 있을 떄
# pq[0] : 제일 작은 값
# row[j] : 현재 값
# ==> "현재 값 > 큐에서 가장 작은 값" 이 성립한다면 row[j]를 큐에 삽입한다.
elif len(pq) == N:
if row[j] > pq[0]:
heapq.heappop(pq)
heapq.heappush(pq, row[j])
# Prioirty Queue에 있는 값 중 가장 작은 값(N번쨰 큰 수)
print(pq[0])
