우선순위 큐 / 힙(heap)

우선순위 큐

- 우선순위가 가장 높은 데이터를 가장 먼저 삭제하는 자료구조

- 데이터를 우선순위에 따라 처리하고 싶을 때 사용

자료구조	추출되는 데이터
스택(Stack)	가장 나중에 삽입된 데이터
큐(Queue)	가장 먼저 삽입된 데이터
우선순위 큐(Priority Queue)	가장 우선순위가 높은 데이터

 

 

우선순위 큐를 구현하는 법

   1) 리스트를 이용하여 구현

   2) 힙을 이용하여 구현

 

 

데이터의 개수가 N개일 때, 구현 방식에 따라서 시간 복잡도를 비교

우선순위 큐 구현방식	삽입 시간	삭제 시간
리스트	O(1)	O(N)
힙	O(log N)	O(log N)

 

단순히 N개의 데이터를 힙에 넣었다가 모두 꺼내는 작업은 정렬과 동일 (힙 정렬) - 시간 복잡도 O(NlogN)

 

힙의 특징

- 완전 이진 트리 자료구조의 일종

- 항상 루트 노드를 제거함

- 최소 힙: 루트 노드가 가장 작은 값을 가짐

- 최대 힙: 루트 노드가 가장 큰 값을 가짐

 

완전 이진 트리란?

루트 노드부터 시작해 왼쪽 자식 노드, 오른쪽 자식 노드 순서대로 데이터가 차례대로 삽입되는 트리

 

힙에 원소 추가 / 삭제

heapq 모듈의 heappush() 함수를 이용하여 힙에 원소를 추가할 수 있다. 첫번째 인자는 원소를 추가할 대상 리스트이며 두번째 인자는 추가할 원소를 넘긴다.

from heapq import heappush

heappush(heap, 4)
heappush(heap, 1)
heappush(heap, 7)
heappush(heap, 3)
print(heap)

[1, 3, 7, 4]

 

heapq 모듈의 heappop() 함수를 이용하여 힙에서 원소를 삭제할 수 있다. 원소를 삭제할 대상 리스트를 인자로 넘기면, 가장 작은 원소를 삭제 후에 그 값을 리턴한다.

from heapq import heappop

print(heappop(heap))
print(heap)

1
[3, 4, 7]

 

 

최대 힙 구현

heapq 모듈은 최소 힙의 기능만을 동작한다.

따라서 최대 힙을 만들려면 각 값에 대한 우선 순위를 구한 후, (우선 순위, 값) 구조의 튜플을 힙에 추가하거나 삭제하면 된다.

from heapq import heappush, heappop

nums = [4, 1, 7, 3, 8, 5]
heap = []

for num in nums:
  heappush(heap, (-num, num))  # (우선 순위, 값)

while heap:
  print(heappop(heap)[1])  # index 1

8
7
5
4
3
1

 

출처: https://youtu.be/AjFlp951nz0