<자료구조> 우선순위 큐

 

1. 우선순위 큐(Priority Queue)

* 우선순위 큐

 - 우선순위 큐는 큐와 달리 우선순위가 높은 것부터 Dequeue를 시키는 자료구조를 의미한다.

 

 - 이 장에서는 파이썬 모듈 heapq를 이용하여 구현해보자.

 

* 힙(heap)

 - 힙은 완전이진트리(complete binary tree)를 기본으로 하는 자료구조이다.

 

 - 힙은 부모-자식 노드의 키값 대소 관계가 일정하게 유지된다.

 

 - 최대 힙 : 자식 노드의 키 값보다 부모 노드의 키 값이 항상 크다.

 

 - 최소 힙 : 자식 노드의 키 값보다 부모 노드의 키 값이 항상 작다.

 

최소 힙

 - 참고로 파이썬에서 heapq모듈은 최소 힙 자료구조만 제공한다.

 

2. 구현하기

* 생성

 - 먼저 모듈을 불러와야 한다.

 

import heapq

heap = []

 

 - 모듈을 불러오고 별도의 선언 없이 리스트를 만든다. 이 리스트를 인자로 넘겨 최소힙을 구현할 것이다.

 

 - 기존 리스트를 힙으로 변환하는 방법은 다음과 같다.

 

import heapq

heap = [1,4,8,2,7]
heapq.heapify(heap)
print(heap) #[1, 2, 8, 4, 7]

 - 이 때 최소힙리스트의 가장 앞은 최솟 값이다. 

 

 - 첫 번째 인덱스가 최솟값이라고 리스트가 순서대로 정렬된 것은 아니라는 점에 유의하자.

 

* 추가

 - 비어 있는 힙에 원소를 추가해보자.

 

import heapq

heap = []
heapq.heappush(heap, 1)
heapq.heappush(heap, 4)
heapq.heappush(heap, 8)
heapq.heappush(heap, 2)
heapq.heappush(heap, 7)

print(heap) # [1, 2, 8, 4, 7]

 

 - 원소추가는 heappush 메서드를 통해 이루어진다. 첫 번째 인자는 리스트, 두 번째 인자는 원소를 넣는다.

 

 - 이 때 원소를 추가할 때마다 내부적으로는 이진 트리에 원소를 추가하는 O(logN)의 시간 복잡도를 가진다.

 

 - heapfy또한 내부적으로 위와 같은 과정을 거친다. 따라서 heapfy의 시간 복잡도는 원소 갯수에 따라 바뀌는 O(N)이다.

 

* 삭제(반환)

 - 삭제는 heappop메서드를 통해 이루어진다.

 

import heapq

heap = [1,4,8,2,7]
heapq.heapify(heap)

print(heapq.heappop(heap)) # 1
print(heapq.heappop(heap)) # 2
print(heapq.heappop(heap)) # 4

 

 - pop을 할 때마다 가장 작은 숫자가 삭제되고 반환된다. 그 때마다 그 다음 작은 숫자가 인덱스0이 되며, 내부적으로 이진트리에서 원소를 삭제하여 O(logN)의 시간 복잡도를 갖는다.

 

3. 최대 힙

 - 최소 힙만 제공하는 heapq모듈에서 최대 힙을 구현하려면 어떻게 해야할까?

 

 - 이 때는 원소를 튜플을 이용한다. 최소 힙은 튜플 내 첫 번째 값을 기준으로 힙을 구성한다. 따라서 첫 번째 원소에 -를 붙여 넣으면 된다.

 

import heapq

lst = [1,4,8,2,7]
heap = []

for i in lst:
    heapq.heappush(heap, (-i, i))

while heap:
    print(heapq.heappop(heap)[1], end=' ')

# 8 7 4 2 1 

 

 - 위와 같이 우선순위를 결정하는 기준에 -를 주고 pop을 할 때에는 인덱스 1에 있는 원소를 출력하기만 하면 된다.

 

 

---

 

 

참고

 

201221 개발일지(14일차) - 스택과 큐(3) : 오늘은 우선순위 큐(Priority Queue) + 파이썬에서 heapq로 우선

 

[파이썬] heapq 모듈 사용법