[백준/python] 1927번 최소 힙 - heapq 기능 정리

1. 문제

우선순위 큐, 힙큐를 활용하여 풀어야 하는 문제.

 

2. 풀이

heapq의 기본적인 동작, heappush와 heappop만 활용하면 되는 문제이다.

 

- heapq.heappush(배열 이름, 원소)

- heapq.heappop(배열 이름)

 

이 두 가지만 알면 이 문제를 쉽게 풀 수 있다.

단, 평소에 사용하던 기본 리스트나 deque의 사용법과는 좀 달라서 주의가 필요하다.

 

3. 코드

import heapq
import sys
input = sys.stdin.readline

n = int(input())
arr = []
for i in range(n):
    x = int(input())
    if x == 0:
        if len(arr):
            print(heapq.heappop(arr))
        else:
            print(0)
    else:
        heapq.heappush(arr, x)

 

4. 개념 정리

 

https://docs.python.org/3/library/heapq.html

heapq — Heap queue algorithm

 

사이트를 참고해 heapq의 모든 기능을 정리해보았다.

 

1. heapq.heappush(힙, x)

heap 안에 x 넣기

2. heapq.heappop(힙)

heap에서 가장 작은 항목을 꺼내서 반환함

단, 힙이 비어 있으면 IndexError

cf. 항목을 꺼내지 않고 액세스만 하려면 heap[0] 사용

3. heapq.heappushpop(힙, x)

heap에 x 넣고 가장 작은 항목 꺼내고 반환

heappush + heappop 합쳐 더 효율적

4. heapq.heapify(리스트)

리스트를 heap으로 변환

5. heapq.heapreplace(힙, x)

힙에서 가장 작은 항목 꺼내고 반환한 후 x 넣기

힙 크기가 고정됨

단, 힙이 비어 있으면 IndexError

6. heapq.merge(*iterables, key=None, reverse=False)

여러 개의 입력을 하나로 병합하여 반환

sort와 비슷함

7. heapq.nlargest(n, key=None, reverse=False)

가장 큰 n개의 요소가 포함된 목록을 반환

8. heapq.nsmallest(n, key=None, reverse=False)

가장 작은 n개의 요소가 포함된 목록을 반환

cf. 그러나 n == 1이면 min(). max()를,

n이 큰 값이면 sorted()를 쓰는 것이 더 효율적