자료구조 우선순위 큐(Priority Queue)와 힙(heap)

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

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

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

우선순위 큐(Priority Queue)를 구현하는 방법에는

• 단순 리스트를 이용하여 구현하는 방법
• 힙(heap)을 이용하여 구현하는 방법이 있다.

데이터의 개수가 N개 일때, 구현 방식에 따라서 시간 복잡도를 비교한 내용은 아래와 같다.

• 단순 리스트를 이용하면 삽입에는 O(1), 삭제에는 O(N) 의 시간 복잡도를 가진다.
• 힙(heap)을 이용하면 삽입에는 O(logN), 삭제에는 O(logN)의 시잔 복잡도를 가진다.

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

힙의 특징

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

완전 이진 트리 자료구조(Complete Binary Tree)란?
루트노드(root node) 부터 시작해서 왼쪽 자식 노드, 오른쪽 자식 노드 순서대로 데이터가 삽입되는 트리(tree)를 의미한다.

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

사진 출처 https://alloc.tistory.com/7

• 최소 힙(min heap)
  
  • 루트 노드(root node)가 가장 작은 값을 가진다.
  • 따라서 값이 작은 데이터가 우선적으로 제거된다.
• 최대 힙(max heap)
  • 루트 노드(root node)가 가장 큰 값을 가진다.
  • 따라서 값이 큰 데이터가 우선적으로 제거된다.

힙에 새로운 원소가 삽입되면

새로운 원소가 삽입되면 O(logN)의 시간 복잡도로 힙 성질을 유지하도록 할 수 있다.

힙에 원소가 제거되면

새로운 원소가 삽입되면 O(logN)의 시간 복잡도로 힙 성질을 유지하도록 할 수 있다.

 

파이썬 heapq라이브러리 함수

• heapq.heappush(heap, item) : item을 heap에 추가한다.
• heapq.heappop(heap) : heap에서 가장 작은 원소를 pop & 리턴. 비어 있는 경우 IndexError가 호출된다.
• heapq.heapify(x) : 리스트 x를 즉각적으로 heap으로 변환함 (in linear time, O(N) )

파이썬의 경우, heapq 라이브러리를 사용하면 기본적으로 minheap 성격을 가지고 있다.

import sys
import heapq
input = sys.stdin.readline

def heapsort(iterable):
	h = []
    result = []
    for i in iterable:
    	heapq.heappush(h,i)
    for i in range(len(h)):
    	result.append(heapq.heappop(h))
    return result
    
n = int(input())
data = []
for i in range(n):
	data.append(int(input())
res = heapsort(data)

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

만약에 maxheap으로 구현하려면 push할때랑 pop할때, -를 붙여서 데이터를 push하고 pop하면 된다.

heap_items = [1,3,5,7,9]

max_heap = []
for item in heap_items:
  heapq.heappush(max_heap, (-item, item))

print(max_heap)