백준 1927번 최소 힙

최소 힙 문제로 이전 문제 최대 힙과 같은 문제이다 최대 힙을 구현할때는 음수로 지정해서 힙에 넣었지만 이번에는 그냥 넣으면 최소 힙이 바로된다

 

우선 순위 큐

우선 순위 큐란 일반적인 큐(FIFO)와 다르게 들어간 순서와 상관없이 우선순위가 높은 데이터가 먼저 나오는 큐이다

우선 순위 큐는 힙구조로 구현이 되어있다 우선 순위 큐 EX)최대 힙, 최소 힙

 

 

문제 해결

import sys, heapq

min_heap = []

n = int(sys.stdin.readline().strip())

for i in range(0,n):
    x = int(sys.stdin.readline().strip())
    if x == 0:
        if len(min_heap) == 0:
            print(0)
        else:
            print(heapq.heappop(min_heap))
    else:
        heapq.heappush(min_heap,x)

 

heapq 사용법

추가 heapq.heappush(힙이름, 원소) 를 통해서 원소를 힙에 추가한다

삭제후 리턴 heapq.heappop(힙이름, 원소) 원소를 힙에서 pop

리스트를 힙으로 변환 heapq.heapify(힙이름) 리스트를 힙으로 변환