[Python-CodingTest] 5-11. 최대힙

최대힙

최대힙은 완전이진트리로 구현된 자료구조이며, 부모노드값이 왼쪽 자식과 오른쪽 자식노드의 값보다 크게 구성된다.
따라서 루트노트에는 입력된 값들 중 가장 큰 값이 저장되어 있다.

문제 정리

입력

5
3
6
0
5
0
2
4
0
-1

처리 과정

1. 임포트한 heapq는 default가 최소힙이기 때문에 heapq를 이용해 최대힙을 구현하기 위해서는…
2. heappush()할 때 부호를 반대로
3. heappop()할 때 -를 붙여서 양수로 출력

출력

6
5
5

풀이

import sys
import heapq as hq # 힙큐는 default가 "최소힙"
sys.stdin = open("./input/in11.txt", "r")

lst=[] # 최대힙을 구현할 빈 리스트 생성

while True:
    n=int(input())
    if n==-1:
        break
    if n==0:
        if len(lst)==0:
            print(-1)
        else:
            res=hq.heappop(lst)
            print(-res) # 🌟 출력할 때 부호를 다시 반대로
    else:
        hq.heappush(lst,-n) # 🌟 최소힙의 방식으로 최대힙을 구현하기 위해 넣을 때 부호를 반대로!

정리

• 최대힙을 구현하기 위해서 hq.heappush(lst,-n) 방식으로 -n을 push
• 출력할 때에는 print(-hq.heappop(lst)) 방식으로 양수 형태로 출력

---

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

맨 위로 이동하기