#8 우선순위 큐(heapq)

 힙(heap)은 느슨한 정렬상태를 유지하여 루트 노드에 항상 최대, 혹은 최소값이 오도록 하는 트리형

자료구조이다. 이 구조를 활용하여 삽입된 데이터중 보다 우선순위가 높은 것을 먼저 반환하는

우선순위 큐를 구현할 수 있다.

파이썬에서는 heapq 모듈에 정의된 함수를 사용하여 리스트를 우선순위 큐로 사용한다.

 

import heapq

q = []

heapq.heappush(q, 3)
heapq.heappush(q, 1)
heapq.heappush(q, 8)

for _ in range(len(q)):
 print(heapq.heappop(q), end=' ') # 결과: 1 3 8

 위 코드와 같이 heappush() , heappop() 함수를 통해 힙을 유지하며 삽입하고 최소값을 우선적으로 반환받을 수 있다.

heapq는 기본적으로 최소 힙이며 최대 힙을 구현하고싶을 경우 키 값을 음수형태로 취하는 방식을 사용할 수 있다.

 

heappop()은 O(1)의 시간복잡도를, heappush()는 O(logN)의 시간 힙(heap)은 느슨한 정렬상태를 유지하여 루트 노드에 항상 최대, 혹은 최소값이 오도록 하는 트리형 자료구조이다.

이 구조를 활용하여 삽입된 데이터중 보다 우선순위가 높은 것을 먼저 반환하는 우선순위 큐를 구현 가능하다.

파이썬에서는 heapq 모듈에 정의된 함수를 사용하여 리스트를 우선순위 큐로 사용할 수 있다.

 

import heapq

q = []
heapq.heappush(q, 3)
heapq.heappush(q, 1)
heapq.heappush(q, 8)
for _ in range(len(q)):
	print(heapq.heappop(q), end=' ') # 결과: 1 3 8

 위 코드와 같이 heappush() , heappop() 함수를 통해 힙을 유지하며 삽입하고 최소값을 우선적으로 반환받을 수 있다.

heapq는 기본적으로 최소 힙이며 최대 힙을 구현하고싶을 경우 키 값을 음수형태로 취하는 방식을 사용할 수 있다.

heappop()은 O(1)의 시간복잡도를, heappush()는 O(logN)의 시간복잡도를 가진다.

 

값의 삭제 없이 최소값을 확인만 하고싶은 경우 단순히 인덱스 0 을 참조하면 된다.

 

기존에 값이 들어있는 리스트를 힙으로 사용하려면 heapq.heapify(<리스트>) 함수를 사용할 수 있다.

heapify() 함수는 리스트의 요소들을 하나하나 heappush()한 것과 같은 결과를 내며 O(N)의 시간복잡도를 가진다.