#8 우선순위 큐 (heap)

힙 자료구조 (heapq)

- 특정한 규칙을 가지는 트리로, 최댓값과 최솟값을 찾는 연산을 빠르게 하기 위해 고안된 완전 이진트리를 기본으로 함

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

힙에서는 가잔 낮은 (혹은 높은) 우선순위를 가지느 노드가 항상 루트에 오게 되고, 이를 이용하여 우선순위 큐와 같은 추산적 자료형 구현 가능

이때 키값의 대소 관계는 부모/자식 간에만 성립하고, 형제노드 사이에는 대소 관계가 정해지지 않음

heapq 함수 사용하기

- heapq.heappush(heap, item): item을 heqp에 추가 - heapq.heappop(heap): heap에서 가장 작은 원소를 pop & 리턴, 비어 있는 경우 에러. - heapq.heapify(x): 리스트 x를 즉각적으로 heap으로 변환

import heapq

heap = []
heapq.heappush(heap, 50)
heapq.heappush(heap, 10)
heapq.heappush(heap, 20)

print(heap) # [10, 50, 20]

• heap이라는 빈 리스트를 생성하고, 50, 10, 20을 각각 추가하는 예시

result = heapq.heappop(heap)

print(result) # 10
print(heap) # [20,50]

최대 힙 만들기

• 힙에 원소를 추가할 때 (-item, item)의 튜플 형태로 넣어주면 튜플의 첫 번째 원소를 우선순위로 힙을 구성
• 이때 원소 값의 부호를 바꿨기 때문에, 최소 힙으로 구현된 heapq 모듈을 최대 힙 구현에 활용

heap_items = [1,3,5,7,9]

max_heap = []
for item in heap_items:
  heapq.heappush(max_heap, (-item, item))

print(max_heap) [(-9,9), (-7,7), (-3,3), (-1,1), (-5,5)]

---

국회의원 선거

문제

• 사람들을 매수해서 다솜이가 국회의원 선거에 당선되게 하면 됨
• 매수하는 사람의 최솟값 구하기

입력

• N : 후보의 수 N <= 50
• 둘째 줄 ~ : 기호 1번을 찍으려는 사람 수 ~ 기호 N번을 찍으려는 사람 수
• 득표수 <= 100

출력

• 다솜이가 매수해야 하는 사람의 최솟값 출력

# 다솜이가 매수해야 하는 사람의 최솟값

import sys
input = sys.stdin.readline

import heapq

N = int(input()) # 후보 수
dasom = int(input())

vote = []
count = 0

for _ in range(N-1):
    n = int(input())
    heapq.heappush(vote, -n)

res = 0
while vote:
    n = -heapq.heappop(vote)
    if dasom > n:
        break
    dasom += 1
    res += 1
    heapq.heappush(vote, -(n-1))
    print(vote)
print(res)

• 최대 힙으로 구현, 다솜이가 다른 후보들보다 표가 많아질 때까지 가장 많은 표를 가진 후보의 표를 한 표 감소