백준 11279번 최대 힙

이번 문제는 우선 순위 큐를 이용한 문제이다 우선순위 큐에서 최대 힙을 이용한다 파이썬에 내장된 함수 heapq를 이용해서 쉽게 풀 수 있었다

 

우선 순위 큐

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

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

 

 

문제 해결

import sys, heapq

max_heap = []

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

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

 

heapq 사용법

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

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

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