파이썬 알고리즘 041 | 최소힙

41. 최소힙

최소힙은 완전이진트리로 구현된 자료구조입니다. 그 구성은 부모 노드값이 왼쪽자식과 오른
쪽 자식노드의 값보다 작게 트리를 구성하는 것입니다. 그렇게 하면 트리의 루트(root)노드는
입력된 값들 중 가장 작은 값이 저장되어 있습니다. 예를 들어 5 3 2 1 4 6 7순으로 입력되
면 최소힙 트리는 아래와 같이 구성됩니다.
1
2 3
5 4 6 7
최소힙 자료를 이용하여 다음과 같은 연산을 하는 프로그램을 작성하세요.
1) 자연수가 입력되면 최소힙에 입력한다.
2) 숫자 0 이 입력되면 최소힙에서 최솟값을 꺼내어 출력한다.
(출력할 자료가 없으면 -1를 출력한다.)
3) -1이 입력되면 프로그램 종료한다.
▣ 입력설명
첫 번째 줄부터 숫자가 입력된다. 입력되는 숫자는 100,000개 이하이며 각 숫자의 크기는 정
수형 범위에 있다.
▣ 출력설명
2) 연산을 한 결과를 보여준다.
▣ 입력예제 1
5
3
6
0
5
0
2
4
0
-1
▣ 출력예제 1
3
5
2

<내 풀이>

• 힙으로 푼게 아니라 그냥 야매로 푼 느낌이다

a=[]
while True :
    k=int(input())
    if k==0:
        if len(a)==0:
            print(-1)
        print(min(a))
        a.clear()
        
    elif k==-1:
        break
    else:
        a.append(k)
        

<풀이>

import heapq as hq #hq로 받아줘서 간략하게 받아주기
a=[] #우선, 빈 리스트가 하나 필요
while True:
    n=int(input())
    if n==-1:
        break
    if n==0:
        if len(a)==0:
            print(-1)
        else :
            print(hq.heappop(a)) #a에서 root node값을 출력해줌
    else : 
        hq.heappush(a, n) #새로운 값을 푸쉬해주는 것 - a라는 리스트에다가 n값을 푸쉬해라

<반성점>

• 힙을 몰라서 너무 야매로 풀었다. 힙을 잘 기억하고 잘 적용해서 쓰도록 하자

<배운 점>

• 동그라미는 노드, 각 줄을 레벨이라고 한다, 밑 줄일수록 밑 레벨
• 부모랑 계속 비교하면서 올라가는 거 = 업힙
• 힙에서 pop을 하면 가장 맨 위의 힙(여기선 최소힙)이 나오고 사라짐
• 이렇게 사라진 최소힙의 자리는 맨 밑의 레벨의 오른쪽에서 새로 메꿔준다
• 새로 최소힙(루트힙)이 자리에 온 애는 또 자식노드들이랑 비교하면서 다운힙 진행
• 새로운 힙이 들어온 거라면(푸쉬된거라면) 얘는 자기 부모노드들이라 비교하면서 업힙 진행

힙
import heapq as hq (식에서 쓰기 편하게 하려고 as hq로 받아준다)
리스트도 하나 생성해주기 (ex : a=[])
heappop : 루트힙 가져와주기
(hq.heappop(a))

heappush : 새로운 힙을 넣어주기
(hq.heappush(a, n)) / (값을 넣을 리스트, 넣을 값)