1. 개요

- heapq 모듈의 heappush(), heappop() 함수를 사용하여 리스트를 힙처럼 사용할 수 있고, 이러한 특성을 이용하여 리스트로 우선순위 큐를 구현할 수 있다.

- 구체적으로, heappush() 함수의 인자로 리스트와 그 리스트에 넣을 원소를 넣으면 그 리스트에 그 원소가 삽입되면서 그 결과로 그 리스트가 min-heap이 되고, heappop() 함수의 인자로 리스트를 넣으면 그 리스트의 0번 인덱스에 있는 원소가 삭제되면서 그 min-heap의 그 다음으로 작은 원소가 0번 인덱스로 올라오게 된다.

2. 구현

1
2
3
4
5
6
7
8
9
10
11

from heapq import heappop, heappush

list1 = []

heappush(list1, 10)
heappush(list1, 5)
heappush(list1, 2)

print(heappop(list1), list1)
print(heappop(list1), list1)
print(heappop(list1), list1)

위 코드의 출력 결과는 다음과 같다.

2 [5, 10]
5 [10]
10 []

3. 한 원소가 여러 개의 값을 갖는 우선순위 큐

1
2
3
4
5
6
7
8
9
10
11

from heapq import heappop, heappush

list1 = []

heappush(list1, [10, "사과"])
heappush(list1, [5, "배"])
heappush(list1, [2, "포도"])

print(heappop(list1), list1)
print(heappop(list1), list1)
print(heappop(list1), list1)

- heappush() 함수의 두 번째 인자로 리스트, 튜플 같은 변수형인 변수를 넣으면 삽입/삭제 때마다 그 변수의 0번 인덱스를 기준으로 min-heap을 만들게 된다. 위 코드의 출력 결과는 다음과 같다.

[2, '포도'] [[5, '배'], [10, '사과']]
[5, '배'] [[10, '사과']]
[10, '사과'] []

4. 내림차순 우선순위 큐

- heappush(), heappop() 함수가 지원하는 힙은 min-heap뿐이므로, 내림차순 우선순위 큐를 구현하고자 할 때는 heappush() 함수의 두 번째 인자에 넣는 변수의 0번 인덱스에 ‘실제로 비교하고자 하는 기준값’에 -1을 곱한 값을 대입하여 내림차순 우선순위 큐를 구현할 수 있다.

1
2
3
4
5
6
7
8
9
10
11

from heapq import heappop, heappush

list1 = []

heappush(list1, (-10, 10))
heappush(list1, (-5, 5))
heappush(list1, (-2, 2))

print(heappop(list1)[1], list1)
print(heappop(list1)[1], list1)
print(heappop(list1)[1], list1)

위 코드의 출력 결과는 다음과 같다.

10 [5, 2]
5 [2]
2 []