[algo] 우선순위 큐(Priority Queue)란?

letsbebrave·2022년 4월 11일

스택과 큐 알고리즘 코딩테스트 힙

algorithm

목록 보기

6/16

우선순위 큐

우선순위 큐에서, 높은 우선순위를 가진 원소는 낮은 우선순위를 가진 원소보다 먼저 처리된다. 같은 우선순위를 가진다면, 먼저 들어온 원소를 처리한다.

제거될 때는 가장 작은 값을 제거하는 독특한 특성을 지닌 자료구조

우선순위 큐는 힙(heap)이라는 자료 구조를 통해 구현할 수 있다.

우선순위 큐는 최소한 두 가지 연산이 지원되어야 한다.

하나의 원소를 우선순위를 지정하여 추가하는 함수(push)
가장 높은 우선순위를 가진 원소(가장 작은 원소)를 큐에서 제거하고 반환하는 함수(pop)

힙

완전 이진 트리(Complete Binary Tree)로, 부모 노드의 값이 항상 자식 노드들의 값보다 크거나(Max Heap), 작아야(Min Heap) 한다. 힙은 우선순위 큐를 구현하거나, 힙 정렬을 하는 데 사용된다. 루트 노드에 있는 값이 최대값, 혹은 최소값이며, 자식 노드들의 값의 위치는 기본적인 조건만 맞추면 된다.

파이썬에서 우선순위 큐

모듈이 제공됨

PriorityQueue

from queue import PriorityQueue

q = PriorityQueue() 
q1 = PriorityQueue(maxsize=10) # maxsize를 활용하면 크기 제한 가능

put

.put(item)

que.put(4)
que.put(1)
que.put(7)
que.put(3)
q1.put((1, 'apple')) # (우선순위, 값)의 형태로 저장할 수도 있음

get

원소를 제거할 땐 가장 작은 값을 먼저 제거해줌!
.get()

# 원소 삭제 및 반환
print(que.get())  # 1
print(que.get())  # 3
print(que.get())  # 4
print(que.get())  # 7
q1.get()[1] # (우선순위, 값)의 형태에서 값 반환

우선순위 설정

우선순위가 작은 것부터 먼저 제거됨!
.put((우선순위, 값))

que.put((3, 'Apple'))
que.put((1, 'Banana'))
que.put((2, 'Cherry'))

print(que.get()[1])  # Banana
print(que.get()[1])  # Cherry
print(que.get()[1])  # Apple

파이썬에서 힙

이진 트리 기반의 최소 힙(min heap) 자료구조를 제공
min heap을 사용하면 원소들이 항상 정렬된 상태로 추가, 삭제됨

즉, min heap 내의모든 원소는 항상 자식 원소들보다 크기가 작거나 같도록 원소가 추가되고 삭제됨!!

모듈 임포트

import heapq
리스트를 마치 최소 힙처럼 다룰 수 있게 도와줌
from queue import PriorityQueue를 쓰지 않고도 import heapq만으로도 리스트를 힙으로 다룰 수 있음!

힙에 원소 추가

heapq.heappush(힙 리스트, 원소)

heapq.heappush(heap, 4)
heapq.heappush(heap, 1)
heapq.heappush(heap, 7)
heapq.heappush(heap, 3)
print(heap) # [1, 3, 7, 4] 
# 원소 추가됐을 때는 따로 오름차순으로 정렬되어서 들어가는 게 아님!
# 원소가 `제거될 때` 하나씩 우선순위로 `정렬`되어서 작은 수부터 pop이 되어 나타난다는 것.

힙에서 원소 삭제

heapq.heappop(heap)
힙에서 원소를 하나씩 삭제(heapq.heappop(heap))해줄 때 우선순위로 정렬되어서 작은 수부터 pop이 되어 나온다는 뜻

import heapq
heap = []
heapq.heappush(heap, 4)
heapq.heappush(heap, 1)
heapq.heappush(heap, 7)
heapq.heappush(heap, 3)
print(heap) # [1, 3, 7, 4]

for i in range(4):
    print(heapq.heappop(heap))
# 1
# 3
# 4
# 7

힙에서 원소 삭제하지 않고 얻기

print(heap[0])

기존 리스트를 힙으로 변환

heapq.heapify(heap)

heap = [4, 1, 7, 3, 8, 5]
heapq.heapify(heap)
print(heap) # [1, 3, 5, 4, 8, 7]

최대 힙

heapq 모듈이 최소 힙의 기능만을 동작하므로 최대 힙으로 만들어주기 위해서는 힙에 튜플을 원소로 추가하거나 삭제하면 됨!!!

(어차피 튜플 내에서 맨 앞에 있는 값을 기준으로 최소 힙(가장 작은 값부터)이 구성되기 때문)

import heapq

nums = [4, 1, 7, 3, 8, 5]
heap = []

for num in nums:
  heapq.heappush(heap, (-num, num))  # (우선 순위, 값)

while heap:
  print(heapq.heappop(heap)[1])  # index 1
# 8
# 7
# 5
# 4
# 3
# 1


from heapq import heappop, heappush

def solution(n, works):
    answer = 0
    h = []
    for i in works:
        heappush(h,-i)

    while h:
        n_work = heappop(h)*(-1)
        if n_work == 0:
            break
        heappush(h, -(n_work - 1))
        n -= 1
        if n == 0:
            break
            
    for i in h:
        answer += i*i

    return answer
    
solution([4, 3, 3],	4)
solution([2, 1, 2],	1)
solution([1,1],	3)