[파이썬] 백준 1927 : 최소 힙

[파이썬] 백준 1927 : 최소 힙

https://www.acmicpc.net/problem/1927

1927번: 최소 힙

실버 2

우선순위 큐, 자료구조

---

파이썬의 heapq 모듈이 최소 힙 자료구조를 제공하고 있다.

 

원소들이 항상 정렬된 상태로 추가되고 삭제되며, 가장 작은 값은 언제나 인덱스 0번째에 위치한다.

또한 모든 원소 k는 항상 2k+1, 2k+2번째 인덱스의 원소보다 크기가 작거나 같도록 정렬된다.

 

코드

import sys; input = sys.stdin.readline
import heapq

N = int(input())
heap = []
for i in range(N):
    h = int(input())
    if h != 0:
        heapq.heappush(heap, h)
    else:
        try:
            print(heapq.heappop(heap))
        except:
            print(0)

 

heapq.heappush(리스트, 값) -> 힙에 원소를 추가한다. 가장 작은 값이 인덱스 0에 위치하고, 모든 원소 k는 원소가 추가될 때마다 2k+1에 위치한 원소들의 값보다 작거나 같음을 만족하도록 정렬된다.

heappush() 함수는 O(logN)의 시간 복잡도를 가진다.

 

heapq.heappop(리스트) -> 가장 작은 원소를 삭제하는 동시에 리스트에 남아있는 값들 중 가장 작은 값을 인덱스 0번 위치로 가져온다.

heappop() 함수는 O(logN)의 시간 복잡도를 가진다.

 

두 번째 작은 값을 얻기 위해서는 heappop()을 통해 가장 작은 원소를 먼저 삭제하고, heap [0]에 접근하는 방식을 이용해야 한다.

 

heapq.heapify(리스트) -> 리스트를 heap구조에 맞게 재배치한다. O(N)의 시간 복잡도를 가진다.