[자료구조] 힙(Heap) / 우선순위 큐(PriorityQueue) 파이썬으로 구현하기

Heap이란

heap의 의미

heap : '무엇인가를 차곡차곡 쌓아올린 더미' 라는 뜻이 있다. 말 그대로 힙은 항상 완전 이진 트리의 형태를 띤다.

우선순위 큐, 나무위키

 

우선순위 큐

데이터를 추가한 순서와 상관없이 데이터를 꺼낼 때 값을 오름차순하여 반환하는 자료구조

Heap 모듈을 통해 구현되어 있으며, 기본적으로 데이터를 정렬된 상태로 보관한다.

 

데이터 처리 속도

데이터의 삽입(put) & 삭제(get) :  O(logN)

완전 이진 트리 구조이기 때문에 트리의 레벨이 늘어나면 노드의 수도 두 배씩 증가한다.

레벨이 늘어날수록 → 노드의 수도 증가한다. 그리고 '이진 트리'이다 = 2의 제곱씩 증가

레벨이 i일 때, i 레벨의 노드수는 2**(i-1)개이다.

 

힙(Heap)의 조건

• 최대 힙 : 자식 노드보다 부모 노드의 값이 크다.
• 최소 힙 : 자식 노드보다 부모 노드의 값이 작다.
• 노드는 왼쪽부터 채워진다. ('완전' 이진 트리이므로)
• 중복을 허용한다.

 

※ 부모 노드는 무조건 자식 노드보다 크거나, 작다는 특징이 있다. 그러므로 최대값이나 최소값 찾기에 최적의 트리라고 볼 수 있다. 힙에서는 큐의 값을 꺼낼 때마다 우선순위에 따라 정렬되어 나오도록 하기 때문이다.

 

우선순위 큐 사용 방법

큐를 파이썬에서 구현하는 방법은 두 가지가 있다.

1. PriorityQueue
   
   • 스레드의 안전을 요구하는 상황에서 사용한다.
   • put / get
   • 클래스이기 때문에 pq, q 등으로 객체를 생성하며, 이를 가지고 연산한다.
2. Heapq
   • PriorityQueue보다 속도가 더 빠르다.
   • heappush / heappop
   • 모듈이기 때문에 이미 만들어놓은 list를 가지고 메소드를 활용하여 연산한다.

 

PriorityQueue

큐 선언하기

from queue import PriorityQueue

q = PriorityQueue()

이렇게 선언한다면 우선순위 큐를 사용할 준비는 끝났다. 

q = PriorityQueue(maxsize = 10)

우선순위 큐의 사이즈는 기본적으로 무한대로 설정되어 있다. 만약 특정한 크기가 필요하다면 maxsize로 사이즈를 조정할 수 있다.

 

큐에 원소 추가하기

q.put(1)
q.put(4)
q.put(2)
q.put(8)

q.put()으로 확인할 수 있다.

 

큐에서 원소 삭제하기

q.get() #1
q.get() #2
q.get() #4
q.get() #8

q.get() 으로 확인할 수 있다.

 

큐의 크기 확인하기

q.put('abc')
q.put('dec')
print(q.size()) #2

q.size() 로 확인할 수 있다.

 

큐가 비었는지 확인하기

q.empty()

 

큐가 가득 찼는지 확인하기

q.full()

 

 

Heapq

from heapq

 

원소 삽입 및 삭제하기

pq = []

heapq.heappush(pq, 1)
heapq.heappop(pq)
# 1

 

반드시 기억하기!

기본적으로 우선순위 큐에서는 튜플의 첫 번째 원소를 기준으로 원소들을 정렬한다.