Python 자료구조: heap

힙(Heap)

• 힙은 데이터의 최대값과 최소값을 빠르게 찾기 위해서 고안된 자료구조! 완전 이진 트리구조를 가진다(최하단 왼쪽 노드부터 채워나가는 트리)

* 힙의 종류

->힙은 최대값을 구하기 위한 구조와 최소값을 구하기 위한 구조로 분류
최대 힙(max heap): 부모 노드의 값은 자식 노드값보다 크거나 같다.
최소 힙(min heap): 보모 노드의 값은 자식 노드값과 같거나 작다.

* 힙과 이진 탐색 트리의 비교

• 공통점
  힙과 이진 탐색 트리는 모두 이진트리 자료구조를 사용한다.
• 차이점
  이진 탐색 트리의 경우
  왼쪽 자식 노드 < 부모 노드 값
  오른쪽 자식 노드 ≧ 부모 노드 값
  탐색을 위해서 사용한다.

* 힙의 경우

최대 힙: 자식 노드값 ≦ 부모 노드값
최소 힙: 자식 노드값 ≧ 부모 노드값
최대 또는 최소값을 검색하기 위해서 사용한다.

* 아래의 그림은 최대 힙의 구조!

-> 보는 것처럼 부모 노드 값이 가장 크다. 밑으로 내려가면서 작아짐.

✍️ 내풀이

import sys
import heapq

a = int(sys.stdin.readline())
heap = []

for i in range(a):
    num = int(sys.stdin.readline())
    if num != 0:
        heapq.heappush(heap, (-num))
    else:
        try:
            print(-1 * heapq.heappop(heap))
        except:
            print(0)

• heapq 라이브러리를 쓰니 한결 편하다. 이 문제가 최소 힙이 아닌 최대 힙을 구하는 문제라 처음에 엄청 헤맸다...^^ 입력받은 num을 heapq에 추가 해줄 때 num에 '-'를 붙이고 heappop을 통해 최소 힙을 뽑아 주면서 거기에 다시 -1을 곱해주어 다시 최댓값으로 만들어 주면 됨..! 🔥
• 동기가 추천해줘서 <알고리즘 도감>이라는 알고리즘 앱을 쓰는데 이걸로 먼저 이해하고 자료구조 공부하면 이해가 너무 쉽다... 쵝오...👏

  • 참고:
    heapq.heappush(heap, item)
    힙 불변성을 유지하면서, item 값을 heap으로 푸시합니다.
    heapq.heappop(heap)
    힙 불변성을 유지하면서, heap에서 가장 작은 항목을 팝하고 반환합니다. 힙이 비어 있으면, IndexError가 발생합니다. 팝 하지 않고 가장 작은 항목에 액세스하려면, heap[0]을 사용하십시오.