힙이란 뭘까?

최대 / 최소 원소를 빠르게 찾을 수 있는 자료구조

O(log N)

• 힙 구성 (Heapify)

• 삽입 (insert)

• 삭제 (remove)

• 정렬 (heapsort) → 최악의 결과가 정렬의 최선의 경우일 경우

• 우선 순위 큐 (priority queue) → 우선 순위에 의해 나온다

파이썬에서 heapq 적용하기

import heapq

heapq.heapify(L) # 리스트 L 로부터 min heap 구성
m = heapq.heappop(L) # min heap L 에서 최솟값 삭제 (반환)
heapq.heappush(L, x) # min heap L 에 원소 x 삽입

프로그래머스에서 예시 풀기

더 맵게

https://programmers.co.kr/learn/courses/30/lessons/42626

import heapq

def solution(scoville, K):
	answer = 0
	heapq.heapify(scoville) # mean heap 의 형태

	# 두 가지 조건이 있으니까 이렇게 true 하고 아래에 추가하는 게 가독성 UP
	while True: 
		min1 = heapq.heappop(scoville)
		if min1 >= K:
			break
		elif len(scoville) == 0: # 모든 음식 경우의 수가 K 보다 낮을 경우
			answer = -1
			break
		min2 = heapq.heappop(scoville)
		new_scoville = min1 + 2 * min2
		heapq.heappush(scoville, new_scoville)
		answer += 1

	return answer