자료구조-Heapq

이론

📖 Heapq?

• 최소 힙의 구조.

✏ push

• heapq.heappush(hq,x)
  힙의 형태를 유지하면서 x값을 push.

import heapq

hq=[]
heapq.heappush(hq,x)

✏ pop

• heapq.heappop(hq)
  힙의 형태를 유지하면서 가장 작은 항목을 제거(pop)하고, 그 값을 반환.
  비어있으면 IndexError가 발생한다.

import heapq

hq=[]
heapq.heappop(hq)

✏ heapify

• heapify(x)
  리스트 arr을 선형시간으로 제자리에서 heap으로 변환시킨다.

import heapq

arr=[1,2,5,4,3]
heapq.heapify(arr) 

문제풀이

📖 백준 1927

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

# keypoint : heapq

import heapq
import sys
input=sys.stdin.readline

n=int(input())

hq=[]
for i in range(n):
    x=int(input())

    # x가 0이면 배열에서 가장 작은 값 출력, 그 값 배열에서 제거.
    if x==0:
        if hq:
            print(heapq.heappop(hq))
        # 배열이 비어있는 경우, 0 출력.
        else:
            print(0)
    # x가 자연수이면 배열에 x 값 추가.
    else:
        heapq.heappush(hq,x)

📖 백준 11279

📌 https://www.acmicpc.net/problem/11279

✏ heapq 를 이용하여 최대 힙을 구현한다.

import heapq

hq=[]
heapq.heappush(hq,-x)
-(heapq.heappop(hq))

# keypoint : heapq

import heapq
import sys
input=sys.stdin.readline

n=int(input())

hq=[]
for i in range(n):
    x=int(input())

    # x가 0이면 배열에서 가장 큰 값 출력, 그 값 배열에서 제거.
    if x==0:
        if hq:
            print(-(heapq.heappop(hq)))
        # 배열이 비어있는 경우, 0 출력.
        else:
            print(0)
    # x가 자연수이면 배열에 x 값 추가.
    else:
        heapq.heappush(hq,-x)