[우선순위 큐 (Priority Queue)]

우선순위 큐 (Priority Queue)

O(logN)의 속도로 자료를 넣었다 뺐다 할 수 있다 
처음에 시간복잡도를 계산하고 O(n^2)이 안될 거 같다 싶으면 쓰기

사용자의 우선순위가 높은 값부터 먼저 출력하는데,
그 우선순위는 정하기 나름이다. 
예를 들어서 max heap이라고 하면, 큰 값이 우선순위가 높고
min heap이라고 하면, 작은 값이 우선순위가 높다. 
그 우선순위는 짝수가 될 수도 있고, 홀수가 될 수도 있다.

우선순위 큐의 안의 내부원리를 살펴보면, 힙이라는 자료구조로 되어있다.
파이썬에서는 import heapq를 사용하는데, 
그렇게 하면 완벽한 이진트리의 형태를 유진하다는 특징이 있다. 


예를 들어 Max heap을 구하는 문제를 살펴보자.
Max heap을 출력하는 방법은 3가지가 있다.

1. 음수를 이용하는 방법
heap에 넣을 때 음수를 곱해서 넣기
heap에서 꺼내서 출력할 때, 배열에 음수를 곱해서 출력하기

2. 튜플을 이용하는 방법
heap에 넣을 때, ( -arr[i], arr[i] )의 형태로 넣기 

3. 배열을 음수처리한 후 heapify를 사용하기
heapq.heapify(heap)
heapify : 주어진 배열(리스트)이나 이진트리를 힙 구조로 재배열하는 것

 

import heapq
arr=[3411,5,3,1,5]
heap=[]
# Maxheap 출력 방법 1 (음수 이용)
for i in range(len(arr)):
    heapq.heappush(heap,-arr[i])
print(heap)

for i in range(len(arr)):
    print(heapq.heappop(heap)*-1) # 또는
    #print(-heapq.heappop(heap))

# Maxheap 출력 방법 2 (튜플이용)
arr=[3411,5,3,1,5]
heap=[]
for i in range(len(arr)):
    heapq.heappush(heap,(-arr[i],arr[i]))
for i in range(len(arr)):
    print(heapq.heappop(heap)[1])

# Maxheap 출력 방법 3 (배열을 음수처리수 heapify 사용하기)
arr=[3411,5,3,1,5]
heap=list(map(lambda x:x*-1,arr))
heapq.heapify(heap)
for i in range(len(heap)):
    print(-heapq.heappop(heap))