[파이썬] 우선순위 큐(Priority Queue), 힙(Heap)

우선순위 큐(Priority Queue)

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

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

 

어떤 물건 데이터를 자료구조에 넣었다가 가치가 높은 물건부터 꺼내서 확인해야 하는 경우에 사용을 한다.

 

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

구현하는 방법에는 두 가지 방법이 있다.

1. 리스트를 이용

2. 힙을 이용

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

 

단순히 N개의 데이터를 힙에 넣었다가 모두 꺼내는 작업은 정렬과 동일하다. 

이것을 힙 정렬이라고 부른다.

이 경우 시간 복잡도는 O(NlogN) 이다. 

 

 

힙(Heap)

최소 힙 예시

힙은 완전 이진 트리 자료구조의 일종이다.

힙에서는 항상 루트 노드를 제거한다.

최소 힙 = 루트 노드가 가장 작은 값을 가진다. = 가장 작은 값이 먼저 삭제된다.

최대 힙 = 루트 노드가 가장 큰 값을 가진다. = 가장 큰 값이 먼저 삭제된다.

서브트리에서도 똑같은 룰이 적용됨 (서브트리의 루트노드가 자식노드들보다 가장 작거나 크다.)

 

힙에 원소가 들어오면 Heapify()라는 함수를 수행하게 된다.

Heapify = 힙의 성질을 만족하도록 수행하는 함수 같은 느낌

이 함수는 최악의 상황에서도 O(logN)의 시간 복잡도로 힙 성질을 유지할 수 있다. 제거 또한 동일하다.

 

구현 코드

# 파이썬의 heapq는 min-heap이다.
import heapq

# 힙(리스트) 생성
heap = []

heapq.heappush(heap, "a")
heapq.heappush(heap, "d")
heapq.heappush(heap, "b")
heapq.heappush(heap, "c")

print(heap)
# 프린트 : ['a', 'c', 'b', 'd']

first = heapq.heappop(heap)
second = heapq.heappop(heap)

print(first) # 프린트 : a
print(second) # 프린트 : b

heap이라는 변수를 리스트로 생성하고

heapq.heappush 메소드를 사용해서 넣어주면 된다.

heapq.heappush 인자로는 첫 번째는 heap 변수, 두 번째는 들어갈 원소를 넣어주면 된다.

그리고 heap에서 빼내고싶다면 heapq.heappop() 메소드를 이용해 원소를 빼낼 수 있다.

우선순위 큐 성질에 의해서 우선순위가 제일 높은 것부터 빠져나오게 된다.

 

위의 예시에서는 a, d, b, c 순으로 넣고, 두 개의 원소를 빼보았다.

그랬더니 첫 번째는 a, 두 번째는 b로 알파벳 순서대로 나오는 것을 볼 수 있다.

default가 min-heap이므로 a , b순임

 

heapq.heappush(heap, "d")
heapq.heappush(heap, [1, "a"])

위와 같이 하나의 heap에 다른 타입의 원소를 넣으려고 하면 오류가 난다!

 

max heap

# 파이썬의 heapq는 min-heap이다.
import heapq

# 넣어야 할 데이터
input_data = [(1, "a"), (4, "d"), (2, "b"), (3, "c")]

# - 연산을 해 준 새로운 데이터를 넣을 리스트
new_data = []

# 넣어야 할 데이터를 - 연산과 함께 new_data에 넣어준다.
for i in input_data:
    new_data.append((-i[0], i[1]))

# print : [(-1, 'a'), (-4, 'd'), (-2, 'b'), (-3, 'c')]
print(new_data)

# 힙(리스트) 생성
heap = []

for j in new_data:
    heapq.heappush(heap, j)

first = heapq.heappop(heap) 
second = heapq.heappop(heap) 
print(first) # (-4, 'd')
print(second) # (-3, 'c')

max heap은 파이썬에서 제공을 해주긴 하지만, push 같은 메소드를 제공을 안해주기 때문에 반쪽짜리이다.

그래서 직접 구현을 해보았다.

 

우선순위를 판별하는 원소에 "-" 연산을 통해서 순서를 뒤집는 것이다.

 

 

참고 사이트

→ medium.com/@yhmin84