[Python-CodingTest] 5-10. 최소힙

최소힙

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

+) 루트노드의 값을 pop 하고 -> 최하위 레벨의 제일 오른쪽 요소를 루트에 올리고 “다운힙”
새로운 요소를 push 하면 -> 최하위 레벨의 오른쪽에 넣은 뒤에 “업힙”

문제 정리

입력

5
3
6
0 // 루트 노드 출력
5
0 // 루트 노드 출력
2
4
0 // 루트 노드 출력
-1 // 종료

처리 과정

1. 최소힙을 구현할 빈 리스트 생성
2. 입력받은 수를 push하기 위해 while문 돌리기
3. 입력받은 수가 -1이면 종료
4. 입력받은 수가 0이면 최솟값(=로트노드 값) pop
5. 그게 아니면 최소힙에 push

출력

3
5
2

풀이

import sys
import heapq as hq # 힙큐 임포트
sys.stdin = open("./input/in10.txt", "r")

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

while True:
    n=int(input())
    if n==-1:
        break
    if n==0: # 최솟값(=루트노드 값)을 꺼내기
        if len(lst)==0: # 최소힙이 비어있는 것
            print(-1)
        else:
            print(hq.heappop(lst)) # 루트노드의 값을 pop
    else: # 값을 push
        hq.heappush(lst,n) # lst에 최소힙의 형태로 n을 push

정리

• 힙큐 임포트: import heapq as hq
• hq.heappush(lst,n): lst에 n을 최소힙의 형태로 push
• hq.heappop(lst): lst에서 루트노드의 값을 pop

---

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

맨 위로 이동하기