[자료구조] 우선순위 큐(Priority Queue), 힙(Heap)

우선순위 큐(Priority Queue)

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

데이터를 자료구조에 넣었다가 우선순위가 높은 순서로 처리하고 싶을 때 사용한다.

 

우선순위 큐는 리스트로 구현하거나 힙(Heap) 자료구조를 이용하여 구현할 수 있다.

먼저 힙을 통해 구현하는 방법을 알기 위해 힙 자료구조에 대해서 알아보자.

---

힙(Heap)

- 힙이란 완전 이진 트리의 일종으로, 부모 노드의 값이 항상 자식 노드들의 값보다 크거나, 작아야 한다.

- 루트 노드가 가장 큰 값을 가지면 최대 힙(Max Heap), 루트 노드가 가장 작은 값을 가지면 최소 힙(Min Heap)이라고 한다. 

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

왼쪽: 최대 힙, 오른쪽: 최소힙

 

힙 구성 함수 heapify()

힙에 원소가 들어오거나 제거되면 heapify()라는 함수를 수행하게 된다. 이는 힙이 항상 힙의 성질을 만족하도록 만들어준다.

 

예를 들어 최소 힙의 heapify()인 경우 부모 노드로 거슬러 올라가며, 부모보다 자신의 값이 더 작은 경우에 위치를 교체한다.

이를 통해 원소가 추가되거나 제거될 때 항상 O(logN)의 시간 복잡도로 힙 성질을 유지하도록 할 수 있다.

 

다시 우선순위 큐의 구현으로 돌아오면 리스트로 구현하는 경우에는 데이터를 리스트에 넣었다가, 꺼낼 때 모든 데이터를 확인하면서 우선순위가 높은 데이터를 삭제하면 되기 때문에 삽입 시간은 O(1), 삭제 시간은 O(N)이다. 반면에, 힙을 이용한 방식은 삽입과 삭제 모두 항상 O(logN)의 시간 복잡도를 갖는다. 

 

힙 정렬(Heap Sort)

또한 힙에 넣었다가 모두 꺼내는 작업은 정렬과 동일하기 때문에 이를 힙 정렬(Heap Sort)이라고 한다. 데이터의 개수가 N개일 때, 힙에 삽입할 때는 O(logN)의 연산을 N번 반복하므로 O(NlogN)이고 삭제할 때도 마찬가지이므로 O(NlogN)이다. 따라서 힙 정렬의 시간 복잡도는 최악의 경우에도 O(NlogN)이 되어 병합 정렬과 함께 일반적으로 가장 빠른 정렬 알고리즘이다.

 

같은 과정을 리스트를 이용해 수행하고자 한다면 시간 복잡도는 O(N^2)이 되기 때문에 대부분의 경우 힙을 이용했을 때 훨씬 빠르게 동작한다. 힙 정렬 원리를 통해 우선순위 큐를 구현하기 때문에 힙이 우선순위 큐를 구현하는 데 가장 많이 사용된다.

 

---

우선순위 큐 파이썬으로 구현하기

대부분의 프로그래밍 언어에서는 우선순위 큐 라이브러리를 지원하기 때문에 일반적인 코딩 테스트 환경에서 우리가 직접 힙 자료구조부터 작성해서 우선순위 큐를 구현할 일은 없다.

 

파이썬에서는 우선순위 큐를 구현할 때 PriorityQueue 라이브러리 또는 heapq 라이브러리를 사용할 수 있는데 일반적으로 heapq가 더 빠르게 동작하기 때문에 heapq를 자주 사용한다. 다만, heapq는 최소 힙 구조만을 지원한다. 따라서 최소 힙을 최대 힙처럼 사용하기 위해서 우선순위에 해당하는 값에 마이너스(-)를 붙여서 넣었다가, 우선순위 큐에서 꺼낼 때 다시 마이너스를 붙여서 원래의 값으로 돌리는 방식을 이용하기도 한다.

 

※ 우선순위 큐를 이용한 힙 정렬 구현

import heapq

def heapsort(iterable):
h = []
result = []
# 모든 원소를 차례대로 힙에 삽입
for value in iterable:
	heapq.heappush(h, value)
    
# 힙에 삽입된 모든 원소를 차례대로 꺼내어 담기
for i in range((len(h)):
	result.append(heapq.heappop(h))
return result

n = int(input())
arr = []

for i in range(n):
	arr.append(int(input()))
    
res = heapsort(arr)

for i in range(n):
	print(res[i])