[Python] 자료구조 - 우선순위큐와 힙(Heap)

[Python] 자료구조 - 우선순위큐와 힙(Heap)

---

1. 우선순위 큐 (PriorityQueue)

• 파이썬에서의 우선순위 큐는 예전 포스트에서 다뤘듯이 queue 라이브러리에 내장되어있는 함수 PrioirtyQueue를 사용하여 쉽게 구현할 수 있다.
• 파이썬에서의 우선순위 큐는 최소값부터 get()하는 Min Heap과 같은 구조를 가지고 있다.

 

1.1. put() & qsize() & get()

• 우선순위 큐에는 input값으로 숫자는 들어갈 수 있지만, 대소비교가 불가능한 str형태 단독은 불가능하다.

Input:

from queue import PriorityQueue
Pque = PriorityQueue()   # que = PriorityQueue(maxsize=8) : 우선순위큐의 사이즈를 8로 제한하고 싶을 때

Pque.put(5)
Pque.put(1)
Pque.put(15)
Pque.put(10)
print(Pque.qsize())

Output:

4

 

Input:

for i in range(Pque.qsize()):
    print(Pque.get())

Output:

1
5
10
15

 

1.2. tuple활용

• 숫자를 오름차순이 아닌 우선순위를 부여하고 싶거나, str형태를 input으로 넣고 싶다면 다음과 같이 튜플을 사용한다.

Input:

from queue import PriorityQueue
Pque = PriorityQueue()

Pque.put((3, 'Apple'))
Pque.put((1, 'Banana'))
Pque.put((2, 'Cherry'))
Pque.put((5, 'Donuts'))
Pque.put((4, 'Egg'))

Pque.qsize()

Output:

5

 

Input:

for i in range(Pque.qsize()):
    print(Pque.get()[1])    # 튜플 구조이므로 인덱스1번을 인덱싱해줌

Output:

Banana
Cherry
Apple
Egg
Donuts

 

 

2. 힙 (Heap)

• 파이썬에서의 힙은 heapq 라이브러리를 통해 힙 관련 함수를 사용할 수 있는데 이는 위의 우선순위 큐와 달리 자료구조 그 자체를 생성하는 것이 아닙니다.
• 힙 객체를 생성한다는 개념으로 알기보다는 그냥 빈 리스트를 생성한 후 이에 힙 관련함수를 적용해 최소 힙 (MinHeap)처럼 다룰 수 있게 해준다고 아는 편이 좋습니다.
• 물론 이미 생성되어있는 리스트도 힙처럼 다룰 수 있게 만들어주는 함수 heapify도 존재합니다.
• 아래에서도 설명하겠지만, str형태의 우선순위를 정하기 위해 튜플을 다뤄야하는 경우에는 우선순위 큐(PriorityQueue)를 사용하는 것이 바람직할 것이다.

2.1. heappush() & heappop()

Input:

import heapq

heap_list = []
heapq.heappush(heap_list, 5)
heapq.heappush(heap_list, 15)
heapq.heappush(heap_list, -5)
heapq.heappush(heap_list, 45)
heapq.heappush(heap_list, 35)
print(heap_list)
print(type(heap_list))

Output:

[-5, 15, 5, 45, 35]
<class 'list'>

• 출력결과를 보면, MinHeap 구조 개념과 같이 최소값을 맨 위의 rootnode에 놓아둔 듯한 모습과 나머지 원소들은 sort가 안 되어있음을 볼 수가 있다.
• 이러한 MinHeap과 같은 특징의 자료구조이지만, 실제 타입은 변함없이 리스트임을 볼 수 있다.

 

Input:

for i in range(len(heap_list)):
    print(heapq.heappop(heap_list))

Output:

-5
5
15
35
45

 

2.2. heapify()

• heapify()함수를 통해 이미 생성된 리스트를 MinHeap 구조로 만들 수 있다. 하지만 이것 역시 MinHeap구조의 특징만을 반영한 것이지, 그 자체는 힙이 아닌 리스트 형태를 유지한다.

Input:

heap = [5, 15, -5, 45, 35]
heapq.heapify(heap)
print(heap)
print(type(heap))

Output:

[-5, 15, 5, 45, 35]
<class 'list'>

• list가 MinHeap 구조를 가지게 되면서 최소값 -5를 찾아 맨위의 rootnode로 놓아두었고, 원래 해당자리에 있던 5가 -5의 자리를 대신하게 됐음을 알 수 있다.

 

Input:

for i in range(len(heap)):
    print(heap.pop(0))
    heapq.heapify(heap)

Output:

-5
5
15
35
45

• list의 pop()메소드와 heapify() 함수를 통해 오름차순으로 숫자를 출력해낼 수 있었다.

 

결론

• 파이썬에서는 str형태 혹은 다른 형태의 자료까지 우선순위를 정할 수 있는 튜플을 넣어 자료구조를 형성하는 queue라이브러리의 우선순위 큐(PriorityQueue)가 범용성이 넓다고 생각한다.
• 파이썬의 우선순위 큐와 힙은 MinHeap의 구조만을 가지고 있다는 문제점이 있다.
• MaxHeap의 구조를 생성하기 위해서는 PriorityQueue를 사용하여 구조를 생성한 후, 우선순위를 나타내는 숫자에 -1을 곱하는 조치를 취하면 될 것이므로 역시 heapq라이브러리
• PriorityQueue에서 사용한 put(), get() 메소드의 시간복잡도는 O(logn)이다.
• heapq라이브러리 안의 함수들의 시간복잡도를 생각해보자면, heappush()와 heappop()은 역시 O(logn)의 시간복잡도를 가지지만, 함수 heapify()는 O(n)의 비교적 높은 시간복잡도를 갖게 된다.
• 따라서, 우선순위 큐 혹은 힙 구조를 새로 생성하고 다루려고 한다면 일반적으로 queue라이브러리의 PriorityQueue를 사용하게 될 것 같다.
• heapq라이브러리를 사용하게 되는 경우는 아마 새로운 힙 구조를 처음부터 생성하는 것이 아닌, heapify를 통해 이미 생성되어있는 리스트를 힙 구조로 바꿔야 할 때, heapq라이브러리를 사용하게 될 것 같다.