Tuple Heap

Tuple Heap은 일반적인 힙과 달리 우선순위와 데이터를 모두 튜플(Tuple) 형태로 저장하는 자료구조임. 이러한 특징으로 인해, 우선순위와 데이터가 모두 필요한 경우에 유용하게 사용될 수 있음.

import heapq as hq
import sys

num = sys.stdin.readline
pq = []
for _ in range(int(num())):
    x = int(num())
    if x:
        hq.heappush(pq, (abs(x), x))
    else:
        print(hq.heappop(pq)[1] if pq else 0)

Max/Min Heap

Max Heap은 부모 노드가 자식 노드보다 항상 큰 값을 가지는 힙 자료구조임. 이러한 특징으로 인해, 최대값을 찾는 작업에 유용하게 사용됨.

Min Heap은 부모 노드가 자식 노드보다 항상 작은 값을 가지는 힙 자료구조임. 이러한 특징으로 인해, 최소값을 찾는 작업에 유용하게 사용됨.

다만 python을 사용할 경우 트리의 루트가 Min Heap 타입임으로 Max Heap으로 구현을 하고 싶을 경우 - 넣어야함.