[김태원 알고리즘] 최소힙

사용 언어: Python3

문제

최소힙 동작 방식

• 푸시하면 -> 업힙
  • 맨 마지막 레벨 왼쪽에 추가. 그리고 부모와 비교하면서 점점 up
• 팝하면 -> 다운힙
  • 루트 노드를 팝하고 맨 마지막 레벨 오른쪽 노드를 루트로 데려옴. 그리고 자식중에 더 작은 값과 비교하면서 점점 down

풀이

import heapq as hq

lst = [] # 힙을 모방할 리스트
while True:
    n = int(input())
    if n == -1:
        break
    if n == 0:
        if len(lst) == 0:
            print('-1')
        else:
            print(hq.heappop(lst)) # ✅ 힙 팝
    else: 
        hq.heappush(lst, n) # ✅ 힙 푸시

---

💛 개인 공부 기록용 블로그입니다. 👻

맨 위로 이동하기