최대힙

최대힙

최대힙 자료를 이용하여 다음과 같은 연산을 하는 프로그램 작성

1) 자연수가 입력되면 최대힙에 입력

2) 숫자 0 이 입력되면 최대힙에서 최댓값을 꺼내어 출력 (출력할 자료가 없으면 -1 출력)

3) -1이 입력되면 프로그램 종료

 

▣ 입력예제

5

3

6

0

5

0

2

4

0

-1

 

▣ 출력예제

6

5

5

---

내가 쓴 코드

import sys
import heapq
sys.stdin = open("input.txt", 'rt')

heap = []

while True:
    n = int(input())
    if n == -1:
        break
    if n == 0:
        if heap:
            print(-heapq.heappop(heap))
        else:
            print(-1)
    else:
        heapq.heappush(heap,-n)

 

모범답안

#모범답안
import sys
import heapq as hq
sys.stdin = open("input.txt",'rt')

a = []
while True:
    n = int(input())
    if n == -1:
        break
    if n == 0:
        if len(a) == 0:
            print(-1)
        else:
            print(-hq.heappop(a))
    else:
        hq.heappush(a, -n)

 

느낀점

1. 이 문제도 힙 모듈 사용 문제

2. 파이썬에서 제공하는 heapq모듈은 최소힙(루트노드가 최솟값)만 있으니까
최대힙(루트노드가 최댓값)은 음수 형태로 넣으면 쉽게 구현 가능!

3. 힙에서 알아야 할 점은.. heappop을 하면 루트노드가 pop되는데
(최소힙에서는 최솟값, 최대힙에서는 최댓값) 이때 리프노드 중 가장 끝 노드가 
루트로 이동하고 heap down되는 형태로 진행됨

heappush하면 리프노드 중 가장 끝 노드로 추가되고,
부모노드와 비교하는 heap up하며 자리를
찾아 올라감

---

 

다시 써보기

#다시 써보자
import sys
sys.stdin =open("input.txt",'rt')
import heapq

max_heap = []

while True:
    n = int(input())
    if n == -1:
        break
    if n == 0:
        if max_heap:
            print(-heapq.heappop(max_heap))
        else:
            print(-1)
    else:
        heapq.heappush(max_heap,-n)