[백준 11286] 파이썬 - 절대값 힙 (heapq 구조 / heappush / heappop)

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

11286번: 절댓값 힙

 

 

1.  heap 이란?

 

우선 순위 큐의 구현 방법은 리스트와 힙(heap)이 있는데 이 둘은 시간복잡도의 차이가 있다.

우선순위 큐 구현 방식	삽입시간	삭제시간
리스트	O(1)	O(N)0
힙	O(logN)	O(logN)

 

 

 

 

2. heapq의 구조

 

heapq.heappush(x,y) : x 배열에 y 원소를 힙 구조로 삽입

heapq.heappop(x) : heappop는 x에 있는 원소의 최솟값을 방출

 

최대 힙(max heap)의 구조

 

 

힙은 완전 이진 트리 자료 구조의 일종이며 파이썬은 최소 힙(min heap) 방식을 사용한다

 

for i in array:

    heapq.heappush(heap,i)

 

    print(heap, i )

단, heappush를 했다고 x가 정렬되는 것이 아님을 알 수있는데

 

heappush에 의해 heap 리스트가 채워지는 과정은 다음과 같다.

 

(정렬을 하고 싶으면 heapify 이용한다)

 

 

 

 

 

for i in range(len(array)):

    print(heapq.heappop(heap),heap, i )

-> heappop 은 단순하게 heap 리스트에 있는 최소값을 pop 해주는데, 이는 정렬에 적용할 수 있다.

 

 

 

3. 백준 풀이

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

 

import heapq

import sys

input = lambda : sys.stdin.readline().strip()

 

n = int(input())

a=[int(input()) for i in range(n)]

h=[]

for i in a: 

  if i == 0: 

      if h: 

        print(heapq.heappop(h)[1]) 

      else: 

        print(0) 

  else: heapq.heappush(h, [abs(i), i])