[백준] # 11286 절댓값 힙(python)

 

 

[Heap 자료구조]

힙 자료구조는 자료구조를 구현하는 기술 중 하나.

- 최대 힙(Max heap): 부모노드가 자식노드보다 값이 큰 완전 이진트리

- 최소 힙(Min heap): 부모노드가 자식노드보다 값이 작은 완전 이진트리

=> 우선순위 큐를 구현하기 위해 만들어진 자료구조

 

내장함수 heapq

heapq.heappush(heap, item)

: item을 heap에 추가.

이때 item을 (item1, item2)와 같은 튜플 형태로 넣어주면 첫번째 원소를 우선순위로 heap을 구성한다.

 -> 이 특성을 이용하면 문제를 쉽게 해결할 수 있다.

 

heapq.heappop(heap)

: heap에서 가장 작은 원소 pop (비어있으면 index error)

 

import sys
import heapq
input = sys.stdin.readline

N = int(input())
q = []
for i in range(N):
    x = int(input())
    if x != 0:
        heapq.heappush(q, (abs(x), x))
    else:
        if not q:
            print(0)
        else:
            a = heapq.heappop(q)
            print(a[1])

 

 

[문제링크]

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