알고리즘 우선순위큐 - 최대 힙(백준 11279번) 파이썬

 

우선순위큐

일반적인 큐(Queue)는 선입 선출의 구조(FIFO, First In First Out)를 가지고 있다.

하지만, 우선순위큐(Priority Queue)는 들어간 순서에 상관없이 우선순위가 높은 데이터가 먼저 나오는 것을 의미한다.

 

 

 

우선순위 큐는,

1. 모든 항목에 우선순위가 있다.

2. 높은 우선순위를 가진 요소는 낮은 우선순위를 가진 요소보다 먼저 제거된다.

3. 두 요소의 우선순위가 같으면 큐의 순서에 따라 제거된다.

 

 

 

우선순위큐는 최소 두 가지 연산을 가지고 있다.

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

 

 

우선순위큐는 힙(heap)이라는 자료 구조를 이용해 구현한다

힙(heap)이란, 완전 이진트리로 부모 노드의 값이 항상 자식 노드들의 값보다 크거나(최대 힙), 작아야(최소 힙) 한다.

 

 

파이썬 우선순위큐

파이썬에서는 PriorityQueue 라는 모듈을 이용해 우선순위 큐를 구현할 수 있다.

하지만  PriorityQueue 는 멀티스레드 환경에서 안전하게 동작되도록 설계되어 있기 때문에,

내부적으로 락(lock) 처리가 되어있으며, 일반적인 heapq 보다 성능이 많이 떨어진다.

 

특히, 백준 문제는 싱글스레드 환경이므로 heapq를 사용하는 것이 더 안정적이다.

또한, PriorityQueue 를 사용하면 큐가 비어있을 때 get을 호출하면  스레드가 멈춰 런타임에러가 발생할 수 있다.

그러므로 백준에서는 heapq를 사용하는 것이 좋다.

 

 

---

 

PriorityQueue

from queue import PriorityQueue

q = PriorityQueue() 

# maxsize를 활용하여 크기 제한
mq = PriorityQueue(maxsize=10)

 

 

put

• .put(item)

q.put(3)
q.put(4)
q.put(1)


# (우선순위, 값)의 형태로 저장 가능 
q1.put((1, 'one'))

 

 

get

• .get()

# 원소 삭제 및 반환
q.get() # 1

# 출력하려면 변수에 담아 사용
num = q.get()
print(num)

 # (우선순위, 값)의 형태로 저장했을 때 값 반환
q1.get()[1]

 

---

heapq

• 최소 힙(Min Heap)의 구조
• 모든 k에 대해 heap[k] <= heap[2*k+1] 또는 heap[k] <= heap[2*k+2] 만족
• 가장 작은 요소가 heap[0]에 위치
• 힙을 만들기 위해서는, 초기화된 리스트 []를 사용하거나, heapify를 통해 값이 들어있는 리스트를 힙으로 변환 가능

import heapq

 

 

 

push

• heapq.heappush(heap, item)
• 힙에 item을 푸시

import heapq
q = []

heapq.heappush(q,3)

 

 

pop

• heapq.heappop(heap)
• 힙 내부의 가장 작은 항목을 제거하고 값을 반환
• q가 비어있을 땐 indexError 발생
• 반환 없이 단순 접근만 하려면 heap[0] 사용

heapq.heappop(q)

 

 

heapify

• heapify(x)
• 리스트 x를 최소 힙 구조로 변환하는 함수
• 기존 리스트의 원소를 제자리에서 정렬하여 힙 속성을 유지하는 리스트로 변환
• O(N)의 시간복잡도
• 힙을 구성할 때 부모 노드에서 자식으로 내려가면서 정렬하는 방식 사용

x = [4, 3, 1, 2, 5, 6]
print(x) # [4, 3, 1, 2, 5, 6]
heapq.heapify(x)
print(x) # [1, 2, 4, 3, 5, 6]

 

• 원래 리스트

    4
   / \
  3   1
 / \  /
2   5 6

 

• 힙 변환 후

    1
   / \
  2   4
 / \  /
3   5 6

 

 

백준 최대힙(11279번, 실버2)

문제 설명

널리 잘 알려진 자료구조 중 최대 힙이 있다. 최대 힙을 이용하여 다음과 같은 연산을 지원하는 프로그램을 작성하시오.

1. 배열에 자연수 x를 넣는다.
2. 배열에서 가장 큰 값을 출력하고, 그 값을 배열에서 제거한다.

프로그램은 처음에 비어있는 배열에서 시작하게 된다.

 

입력

첫째 줄에 연산의 개수 N(1 ≤ N ≤ 100,000)이 주어진다. 다음 N개의 줄에는 연산에 대한 정보를 나타내는 정수 x가 주어진다. 만약 x가 자연수라면 배열에 x라는 값을 넣는(추가하는) 연산이고, x가 0이라면 배열에서 가장 큰 값을 출력하고 그 값을 배열에서 제거하는 경우이다. 입력되는 자연수는 231보다 작다.

 

 

출력

입력에서 0이 주어진 횟수만큼 답을 출력한다. 만약 배열이 비어 있는 경우인데 가장 큰 값을 출력하라고 한 경우에는 0을 출력하면 된다.

 

 

예제입력

13
0
1
2
0
0
3
2
1
0
0
0
0
0

 

예제출력

0
2
1
3
2
1
0
0

 

 

코드1 : PrioirtyQueue(런타임에러)

• 출력값은 맞게 나오지만, 런타임에러 발생
• 멀티스레드 환경에서는 큐가 비어있을 때 get()이 호출되며 에러가 발생할 수 있음(백준은 싱글스레드라 상관없음)
•  PriorityQueue.get()이 내부적으로 블로킹 동작(큐가 비어있을 경우 기본적으로 무기한 대기하는 상태)을 함
• 하지만 백준은 그런 동작을 지원하지 않아 런타임에러 발생
• PrioirtyQueue는 최소 힙을 기본으로 사용하고 있기 때문에 음수로 변환하여 사용하면 최대힙으로 사용 가능 

from queue import PriorityQueue

q = PriorityQueue()
N = int(input())

for _ in range(N) :
    i = int(input())
    if i == 0 :
        if q.empty() :
            print(0)
                   
        else :
            num = -q.get()
            print(num)
    else :
        q.put(-i)

 

 

코드2 : heapq 사용(성공)

• heapq는 최소 힙을 기본으로 하고있기 때문에 음수부호(-)를 사용하면 최대 힙으로 사용 가능
• heapq은 백준과 같은 싱글스레드 환경에서 빠르고 안정적 

# 114208KB, 160ms


import sys
import heapq

input = sys.stdin.readline
q = []

N = int(input().strip())

for _ in range(N) :
    x = int(input().strip())

    if x == 0 :
        if q :
            print(-heapq.heappop(q))
        else :
            print(0)

    else :
        heapq.heappush(q, -x)

 

 

참고 자료 : velog MEIN_FIGUR