백준 최대 힙, 절댓값 힙 - heapq 사용, 파이썬

	import heapq
	import sys
	n = int(input())
	queue = []
	for i in range(n):
	a = int(sys.stdin.readline().rstrip())
	if a > 0:
	heapq.heappush(queue, -a)
	elif a == 0:
	if not queue:
	print(0)
	continue
	print(-heapq.heappop(queue))

view raw 백준 - 최대 힙 hosted with ❤ by GitHub

	import heapq
	import sys
	n = int(input())
	queue = []
	for i in range(n):
	a = int(sys.stdin.readline().rstrip())
	if a == 0:
	if not queue:
	print(0)
	continue
	print(heapq.heappop(queue)[1])
	else:
	heapq.heappush(queue, (abs(a), a))

view raw 절댓값 힙 hosted with ❤ by GitHub

파이썬 내장모듈 heapq는 기본적으로 최소힙을 제공한다. 즉 queue에 원소들은 push한 후 pop을 했을 때 작은 값부터 나온다는 뜻이다. 해당 문제는 자연수 기준이므로 숫자를 음수로 바꾼 뒤 push하고, pop한 후 다시 -를 붙여주면 큰 수부터 출력할 수 있게 된다. 

절댓값 힙은 절댓값과 본값을 가지는 튜플로 heapq를 수행한다. 튜플은 첫번째 원소를 기준으로 정렬되므로 절댓값으로 정렬 후 출력은 두번째 원소를 해주면 된다.