우선순위 큐, 힙(Priority Queue, heap) (백준 문제 포함)

우선순위 큐(Priority Queue)는 큐(Queue)나 스택(Stack)과 비슷한 축약 자료형이다.

일반적인 큐는 FIFO(First in-First Out) 구조이지만 우선순위 큐(Priority Queue)는 들어간 순서에 상관없이 

우선순위가 높은 데이터가 먼저 나오는 구조이다.

파이썬에서는 heapq 또는 PriorityQueue 라이브러리를 사용해서 우선순위 큐를 구현할 수 있다.

import heapq

nums = [4, 1, 7, 3, 8, 5]
heap = []
for n in nums:
    heapq.heappush(heap, n)
while heap:
    print(heapq.heappop(heap))

우선순위 큐(최소 힙)

heapq.heappush를 사용해서 우선순위 큐에 요소를 삽입하고, heapq.heappop을 사용해서 pop 할 수 있다.

heapq는 기본적으로 최소 힙이라서 값이 작은 (1, 3)부터 (3, 1), (10, 2)가 순서대로 pop 되는 것을 확인할 수 있다.

큰 것부터 pop 하고 싶다면 아래 코드와 같이 구현해주면 된다.

import heapq

nums = [4, 1, 7, 3, 8, 5]
heap = []
for n in nums:
    heapq.heappush(heap, (-n, n))
while heap:
    print(heapq.heappop(heap)[1], end=' ')
print()

우선순위 큐(최대 힙)

아래 코드는 PriorityQueue를 사용해서 구현한 우선순위 큐이다.

from queue import PriorityQueue

q = PriorityQueue(maxsize=4)
q.put(3)
q.put(7)
q.put(2)
q.put(9)
print(q.get(), end= ' ')
print(q.get(), end= ' ')
print(q.get(), end= ' ')
print(q.get(), end= ' ')

우선순위 큐는 다익스트라 알고리즘이나, K번 째 최댓값을 찾을 때 등등에 사용할 수 있다.

아래는 대표적인 우선순위 큐 문제 풀이이다.

백준 11279번 최대 힙)

import heapq
import sys
input = sys.stdin.readline

N = int(input()) 
q = []
for _ in range(N):
    n = int(input())
    if n != 0:
        heapq.heappush(q, -n)
    else:
        print(-heapq.heappop(q) if q else 0)

백준 1927번 최소 힙)

import heapq
import sys
input = sys.stdin.readline

N = int(input()) 
q = []
for _ in range(N):
    n = int(input())
    if n != 0:
        heapq.heappush(q, n)
    else:
        print(heapq.heappop(q) if q else 0)

 

백준 알고리즘 문제 풀이)

jinho-study.tistory.com/1006

백준 알고리즘 11279번 최대 힙(python)

jinho-study.tistory.com/1007

백준 알고리즘 1927번 최소 힙(python)

jinho-study.tistory.com/1009

백준 알고리즘 11286번 절댓값 힙(python)

jinho-study.tistory.com/1010

백준 알고리즘 1655번 가운데를 말해요(python)

jinho-study.tistory.com/1024

백준 알고리즘 1417번 국회의원 선거(python)

jinho-study.tistory.com/1026

백준 알고리즘 14235번 크리스마스 선물(python)

jinho-study.tistory.com/1027

백준 알고리즘 15903번 카드 합체 놀이(python)

jinho-study.tistory.com/1067

백준 알고리즘 2075번 N번째 큰 수(python)

jinho-study.tistory.com/1068

백준 알고리즘 1715번 카드 정렬하기(python)