[9] Priority Queue, 우선순위 큐 & Heap, 힙

빠지지 않는 오늘의 짤..

아직도 엄마랑 싸워서 화해 안하고 있음. 근데 안 할거임.

---

사실 큐 포스트 다음이 우선순위 큐였는데 조금 공부하다 보니 트리를 알아야 할 것 같아서 트리를 하고 온 것이다. 

 

2022.04.13 - [Python/[Data Structure] 자료구조] - [6] Queue, 큐

[6] Queue, 큐

 

✅ 우선순위 큐란 

큐에 대해 잠깐 요약해보면 큐는 FIFO, 먼저 들어간게 먼저 나오는, 아틀란티스 줄 구조이다.

하지만, 우선순위 큐는 우선순위를 가지고 있어, 우선순위가 높은 데이터가 먼저 나오는 자료형이다.

우선순위 큐를 배열이나 리스트로 구현할 수 있으나, 삽입 시간이 오래 걸려 힙으로 구현 하는 것이 가장 일반적이다.

 

✅ 힙이란 

힙(Heap)은 완전 이진 트리(Complete Binary Tree)로 트리의 변형된 형태이며, 최대힙(Max Heap)과 최소힙(Min Heap)이 있다.

데이터의 최댓값과 최솟값을 빠르게 찾기 위해 고안되었다. 

 

💎 완전 이진 트리란 

완전 이진 트리 : 노드를 삽입할 때 왼쪽부터 차례로 삽입하는 트리로 마지막 레벨(루트에서 가장 떨어진 줄)을 제외한 모든 노드는 완전히 채워져 있어야 한다.

 

레벨이란

 위의 구조는 완전 이진 트리가 아니다. 5의 자식 노드가 왼쪽 없이, 오른쪽만 존재하기 때문이다.

이렇게 되어 있다면 완전 이진 트리가 맞다. 

 

 

최대힙 : 부모 노드 값이 자식 노드의 값보다 크거나 같고, 완전 이진 트리 형태이다.

최소힙 : 부모 노드 값이 자식 노드의 값보다 작거나 같고, 완전 이진 트리 형태이다.

 

파이썬에서는 heapq 모듈을 제공해주어서 이것을 이용하면 된다. 단, heapq 모듈은 리스트를 최소힙처럼 다룰 수 있게 하기 때문에 최대힙을 구현하고 싶다면 데이터를 음수로 넣어주고 나중에 값을 꺼낼 때 다시 음수 부호를 붙여서 꺼내면 된다.

 

✅ 파이썬 힙 구현 

heapq.heappush(heap, item)	heap에 아이템을 추가함
heapq.heappop(heap)	heap의 가장 작은 아이템을 반환하고 삭제함
heapq.heappushpop(heap, item)	heap에 아이템을 추가하고 가장 작은 아이템을 반환하고 삭제함
heapq.heapify(x)	리스트 x를 heap의 형태로 바꾸어줌
heapq.heapreplace(heap, item)	heap에 가장 작은 아이템을 반환하고 삭제한 후 아이템을 추가함

 

import heapq

minHeap = []

heapq.heappush(minHeap, 10)
heapq.heappush(minHeap,20)
heapq.heappush(minHeap,30)
heapq.heappush(minHeap,40)
heapq.heappush(minHeap,15)
heapq.heappush(minHeap,35)

while minHeap:
    print(heapq.heappop(minHeap), end=' ')
    
# 출력 결과
10 15 20 30 35 40

maxHeap = []

heapq.heappush(maxHeap, -10)
heapq.heappush(maxHeap, -20)
heapq.heappush(maxHeap, -30)
heapq.heappush(maxHeap, -40)
heapq.heappush(maxHeap, -15)
heapq.heappush(maxHeap, -35)

while maxHeap:
    print(-heapq.heappop(maxHeap), end=' ')
    
# 출력 결과
40 35 30 20 15 10

 

✅ 힙의 시간 복잡도 

최대 노드의 개수가 N이면 높이는 log2(N+1)-1이다. 반대로 높이가 h라면 노드의 개수는 2^(h+1)-1개가 된다.

삽입, 삭제 시에 최악의 경우 루트에서 리프까지 비교해서 힙을 만들어야 하므로 O(logn)의 시간 복잡도를 가진다. 

데이터를 꺼내는데에는 O(1), 탐색하는데에는 O(n)의 시간 복잡도를 가진다. 

 

✅ 힙 사용 

힙은 데이터가 최솟값 또는 최댓값으로 계속해서 정렬이 되어야 할 때, 데이터의 삽입과 삭제가 자주 일어날 때 사용된다.

 

✅ 파이썬 우선순위 큐 구현 

파이썬에서는 PriorityQueue 모듈을 지원하고 있다.

 

from queue import PriorityQueue

from pyparsing import empty

PQ = PriorityQueue()

PQ.put(10)
PQ.put(50)
PQ.put(40)
PQ.put(90)

print('Hellow')

while not PQ.empty():
    print(PQ.get(), end=' ')

# 출력 결과
10 40 50 90

 

heapq와 PriorityQueue 의 구현 차이점이 궁금해서 찾아봤는데, queue.PriorityQueue가 heapq을 이용했다는 것 같은데...

어떤 사람 말로는 heapq을 쓰기를 권장한다네여(지나가던 익명의 외국인)

 

https://github.com/Seeun-Lim/Data-Structure/blob/main/Heap.py

GitHub - Seeun-Lim/Data-Structure