문제 / 최대힙 / Python 파이썬

 

문제 제목: 최대힙

---

함수 살펴보기

• heapq.heappush(heap, item): item을 heap에 추가
• heapq.heappop(heap): heap에서 가장 작은 원소를 pop후 return. 비어있는 경우에는 IndexError가 호출된다.
• heapq.heapify(x): 리스트 x를 즉각적으로 heap으로 변환시킨다.

** 힙 함수는 모두 최소힙을 기반으로 작성됨.

최대힙을 구현하려면 음의 부호를 붙여서 push를 해준다.

(pop할 때는 원래 값이 반환되어야하니 한번 더 음의 부호를 넣어준다.)

 

모범답안

import heapq as hq
a = []
while True:
    n = int(input())
    if n == -1:
        break
    if n == 0: # 숫자 0이 입력되면 최소힙에서 최솟값을 꺼내어 출력한다.
        if len(a) == 0:
            print(-1)
        else:
            print(-hq.heappop(a)) # 부호가 반대로해서 push가 됐으니 출력할 때도 -를 붙여줌
    else: # 0 이 아닌 숫자는 push
        hq.heappush(a, -n) # a라는 리스트에 n값을 넣는다.

---

※ 알아야 할 것

-  힙 자료구조에 대한 자세한 내용흔 해당 게시물 참고

https://sillon-coding.tistory.com/149

[자료구조] 우선순위 큐(Priority Queue)와 힙(Heap) / Python 파이썬

 

- 최소힙

https://sillon-coding.tistory.com/196

문제 / 최소힙 / Python 파이썬