힙 (Heap)

- 최댓값 및 최솟값을 찾아내는 연산을 빠르게 하기 위해 고안된 완전이진트리 자료구조

- 힙 속성: A가 B의 부모노드(parent node) 이면 A의 키(key)값과 B의 키값 사이에는 대소관계가 성립

- 최대 힙: 부모노드의 키값이 자식노드의 키값보다 항상 큰 힙

- 최소 힙: 부모노드의 키값이 자식노드의 키값보다 항상 작은 힙

- 키(key)값의 대소관계는 오로지 부모노드와 자식노드 간에만 성립하며 특히 형제 사이에는 대소관계가 정해지지 않음

- 대개 자식노드 개수가 최대 2개인 이진 힙(binary heap)을 사용함

- 데이터의 최대값(최대 힙) or 최소값(최소 힙)을 찾는데 $O(1)$이 소요됨 ---> 루트노드에 저장되어 있으므로

- 데이터의 삽입과 삭제는 $O(\log N)$이 소요됨

- 참고: 자료구조 힙

힙 사용

- 파이썬의 heapq 모듈은 최소 힙이다

- 힙 구조 그림으로 보기 ---> 힙 구조 ---> 이거 보면 무조건 이해 가능

- 힙을 코드로 구현하기 전에 필요한 함수를 공부하자

- heapq.heappush(heap, item) ---> item을 heap에 추가함

- heapq.heappop(heap) ---> heap에서 가장 작은 원소(루트 노드)를 pop(추출)하고 비어 있으면 IndexError

- heapq.heapify(x) ---> 리스트 x를 heap 자료 구조로 변환함

- 참고: heapq

예제: 카드 합체 놀이

- 카드 더미의 최소값 2개를 뽑은다음 두 숫자를 두 수의 합으로 바꿔주는 것을 반복하면 됨

- 최소값 2개를 뽑으면 되니 Heap을 사용하자

- 힙에서 최소값 추출은 $O(1)$ 삽입과 삭제는 $O(logN)$이므로 다른 구조보다 효율적으로 문제를 해결할 수 있음

import heapq

n, m = map(int, input().split())
cards = list(map(int, input().split()))
heapq.heapify(cards) ## list인 cards를 Heap구조로 변홤함

for _ in range(m):
    two_card_sum = heapq.heappop(cards) + heapq.heappop(cards) ## 최소값 2개(제일 작은 값과 두 번째로 작은 값)를 뽑음
    heapq.heappush(cards, two_card_sum) ## 두 수를 두 수의 합으로 바꿔줌
    heapq.heappush(cards, two_card_sum) ## 그리고 cards 에 push한다

print(sum(cards))

19