파이썬 알고리즘 172번 | [백준 11279번] 최대힙

172. 최대힙

1) 어떤 전략(알고리즘)으로 해결?

2) 코딩 설명

<내 풀이>

import heapq
import sys

heap=[]

n=int(sys.stdin.readline().strip())

for i in range(n) :
    inp=int(sys.stdin.readline())
    if inp!=0:
        heapq.heappush(heap,(-inp, inp))

    else : 
        if heap :    
            print(heapq.heappop(heap)[1])
        else :
            print(0)

<반성 점>

import heapq

를 해야지 리스트를 만들고, heapq 사용 가능

<배운 점>

출처 : https://www.daleseo.com/python-heapq/
heapq 는 최소힙으로 구성돼있다고 한다

• 바로 힙에 튜플(tuple)를 원소로 추가하거나 삭제하면, 튜플 내에서 맨 앞에 있는 값을 기준으로 최소 힙이 구성되는 원리를 이용
• 힙에서 값을 읽어올 때는 각 튜플에서 인덱스 1에 있는 값을 취하면 됨
  출처 : https://www.daleseo.com/python-heapq/

heapq.heappush(heap, (-num, num))  # (우선 순위, 값)

• 튜플에서 인덱스 1에 있는 값을 취하면 됨

---

• 나중에 이 힙을 이용해서, 최댓값, 최솟값을 구할 수 있다고 한다.
• K번째 최소값을 구하기 위해서는 주어진 배열로 힙을 만든 후, heappop() 함수를 K번 호출하면 됩니다.