12강 / 20강

힙과 우선순위 큐 — 가장 급한 것이 맨 위로

줄 선 순서가 아니라 중요도 순서로

응급실에 손가락을 벤 사람이 먼저 왔고, 그다음 심장마비 환자가 왔습니다. 큐(FIFO)대로라면 손가락이 먼저겠죠. 하지만 그러면 안 됩니다.

줄 선 순서가 아니라 급한 순서로 꺼내야 하는 상황이 있습니다. 이런 걸 우선순위 큐(priority queue)라고 하고, 이걸 빠르게 만드는 자료구조가 힙(heap)입니다.

🐢 리스트로 만들면

넣기는 빠르지만 꺼낼 때마다
전부 훑어서 최솟값을 찾아야 함
또는 넣을 때마다 정렬 — 역시 느림

⚡ 힙으로 만들면

넣기도 꺼내기도 높이만큼만
1000개여도 약 10번
맨 위는 언제나 최솟값

고등학생가장 급한 것이 맨 위로

7강의 큐는 온 순서대로였습니다. 그런데 급한 것이 나중에 오면요?

순서가 아니라 중요도로 꺼내는 큐

비유 — 응급실

방식	결과
온 순서대로	중상 환자가 기다린다 ⚠
위급한 순서대로	살릴 수 있는 사람을 살린다 ✔

공정함보다 중요도가 앞서는 상황이 있다

어떻게 만들까 — 순진한 방법들

방법	넣기	꺼내기
정렬 유지	O(n) — 자리 찾아 민다	O(1)
그냥 넣기	O(1)	O(n) — 최소를 찾는다
힙	O(log n)	O(log n) ✔

한쪽만 빠른 것보다 둘 다 적당히 빠른 것이 낫다

힙의 규칙 — BST 보다 느슨하다

	BST	힙
규칙	왼 < 나 < 오	나 < 자식들
보장	완전한 정렬	맨 위가 최소만

필요한 것만 보장하니 유지가 싸다

우리가 원하는 건 "가장 급한 것" 뿐입니다. 나머지 순서는 알 필요가 없어요.

덜 약속하면 덜 일해도 된다 — 설계의 지혜

힙의 규칙 — 이진 탐색 트리보다 느슨합니다

최소 힙의 규칙

모든 노드에 대해 — 부모 ≤ 자식. 왼쪽·오른쪽 사이에는 아무 규칙도 없습니다.

11강의 이진 탐색 트리는 완전한 정렬을 유지했지만, 힙은 "맨 위가 최솟값"만 지킵니다. 규칙이 느슨한 대신 유지 비용이 싸요. 우리가 필요한 건 "가장 급한 것 하나"뿐이니까요.

그리고 힙은 빈틈없이 위에서부터 왼쪽부터 채워진 트리라서, 놀랍게도 리스트 하나로 표현할 수 있습니다.

ㅇ번 노드의 부모 → (ㅇ-1) // 2
ㅇ번 노드의 왼쪽 자식 → 2*ㅇ + 1, 오른쪽 자식 → 2*ㅇ + 2

파이썬의 heapq — 리스트 하나가 그대로 힙이 됩니다.

Python 브라우저에서 실행

import heapq

응급실 = []

# (우선순위, 이름) — 숫자가 작을수록 급함
heapq.heappush(응급실, (3, "손가락 베임"))
heapq.heappush(응급실, (1, "심장마비"))
heapq.heappush(응급실, (2, "골절"))
heapq.heappush(응급실, (5, "감기"))

print("힙 내부 모습:", 응급실)
print("↑ 완전히 정렬되어 있지는 않지만, 0번은 언제나 최솟값입니다")
print()

while 응급실:
    순위, 이름 = heapq.heappop(응급실)
    print(f"진료 → {이름} (우선순위 {순위})")

🎮 힙 실험실

값을 넣으면 부모와 비교하며 위로 올라가고(sift-up), 꺼내면 맨 끝 값이 위로 갔다가 아래로 내려옵니다(sift-down). 한 걸음씩 눌러 확인해 보세요.

고등학생힙이 모양을 고치는 법

힙이 어떻게 맨 위 = 최소를 유지하는지 봅시다.

넣고 뺄 때마다 한 줄기만 손본다 — 그래서 log n

넣을 때 — 위로 올라간다

맨 아래 끝에 넣는다
부모보다 작으면 자리를 바꾼다
더 이상 안 작을 때까지 반복

최대 깊이만큼만 올라간다 — 20단계면 100만 개

뺄 때 — 아래로 내려간다

맨 위를 꺼낸다 (답)
맨 아래 끝의 것을 맨 위로 옮긴다
자식보다 크면 작은 자식과 바꾼다
반복

역시 한 줄기만 — 옆으로 퍼지지 않는다

비유 — 물속의 공기방울

작은 값은 가벼워서 위로 뜨고 큰 값은 무거워서 아래로 가라앉습니다.

동작	비유
넣기	바닥에 넣으면 떠오른다
빼기	위를 걷어 내면 다시 정렬된다

전체를 흔들지 않고 한 줄만 정리된다

놀라운 사실 — 힙은 리스트로 만듭니다

트리처럼 보이지만 실제로는 배열 하나예요.

노드	배열 위치
i 번의 왼쪽 자식	2i+1
i 번의 오른쪽 자식	2i+2
i 번의 부모	(i-1)//2

화살표가 필요 없다 — 계산으로 부모와 자식을 찾는다

그래서 메모리도 적게 쓰고 /ca 8강의 캐시도 잘 맞습니다.

고등학생최대 힙이 필요하면

파이썬의 heapq 는 최소 힙만 줍니다. 가장 큰 것을 꺼내려면요?

부호를 뒤집어 넣는다 — 간단한 요령

heapq.heappush(h, -값)      # 넣을 때 마이너스
가장큰값 = -heapq.heappop(h)  # 꺼낼 때 다시 마이너스

왜 통하나

원래	부호 뒤집으면
5, 3, 9	-5, -3, -9
가장 큰 것 = 9	가장 작은 것 = -9

"가장 크다" 가 "가장 작다" 로 뒤집힌다

비유 — 거울

거울 앞에서는 왼쪽이 오른쪽이 됩니다. 거울을 보고 왼쪽으로 가면 실제로는 오른쪽이죠.

도구를 바꾸지 않고 입력을 바꾼다

우선순위와 값을 함께 넣기

실전에서는 튜플을 넣습니다.

heapq.heappush(h, (우선순위, 순번, 작업))

자리	역할
첫째	우선순위 — 이걸로 비교
둘째	순번 — 같을 때 먼저 온 것 우선
셋째	실제 자료

둘째가 없으면 셋째를 비교하려다 오류가 날 수 있다

작업 객체끼리는 크기를 비교할 수 없으니까요. 순번을 넣으면 거기까지 가지 않습니다.

4강의 튜플이 여기서 정확히 쓰인다 — 순서대로 비교

힙의 진짜 위력 — '전부 정렬하지 않고 상위 K개만'

Python 브라우저에서 실행

import heapq

점수 = [88, 95, 76, 100, 64, 91, 82]

print("상위 3명:", heapq.nlargest(3, 점수))
print("하위 3명:", heapq.nsmallest(3, 점수))

# 최대 힙 흉내내기
최대힙 = []
for ㅅ in 점수:
    heapq.heappush(최대힙, -ㅅ)
print("1등:", -heapq.heappop(최대힙))
print("2등:", -heapq.heappop(최대힙))

print()
# 스트리밍 상위 K개 — 전체를 정렬하지 않고도 됩니다
import random
큰데이터 = [random.randint(1, 100000) for _ in range(100000)]
상위5 = []
for ㅅ in 큰데이터:
    heapq.heappush(상위5, ㅅ)
    if len(상위5) > 5:
        heapq.heappop(상위5)          # 가장 작은 것을 버린다
print("10만 개 중 상위 5개:", sorted(상위5, reverse=True))
print("→ 크기 5짜리 힙만 유지했습니다. 10만 개를 정렬할 필요가 없어요.")

고등학생힙을 쓰는 곳

note 의 목록에 왜 그런지를 붙여 봅시다.

① 상위 K개 찾기

100만 개에서 상위 10개를 찾으려면?

방법	비용
전부 정렬	O(n log n) · 메모리 n
크기 10 짜리 힙	O(n log 10) · 메모리 10 ✔

10개만 알면 되는데 100만 개를 정렬할 이유가 없다

② 다익스트라 — 최단 경로

지도에서 가장 짧은 길을 찾을 때, 매번 가장 가까운 곳부터 봐야 합니다.

"가장 작은 것을 계속 꺼낸다" — 힙의 정의 그대로

③ 작업 스케줄러

상황	우선순위
운영체제	프로세스의 급함
메시지 큐	중요도
예약 실행	실행 시각

"가장 빠른 시각" 을 계속 꺼내면 타이머가 된다

④ 병합 정렬의 다중 병합

정렬된 파일 100개를 하나로 합칠 때, 각 파일의 맨 앞 중 최솟값을 계속 꺼냅니다.

힙에 100개만 들고 파일 전체를 합칠 수 있다

공통점

"전체 정렬은 필요 없고 극단값만 계속 필요할 때"

필요한 것	고를 것
전체 순서	정렬 · BST
최솟값만 계속	힙 ✔
있는지만	집합 · 딕셔너리

필요를 정확히 알면 그릇이 정해진다

같은 우선순위일 때 먼저 넣은 것이 먼저 나오게 하는 요령.

Python 브라우저에서 실행

import heapq

# 힙 정렬 — 전부 넣고 전부 꺼내면 끝
def 힙정렬(값들):
    힙 = []
    for ㅇ in 값들:
        heapq.heappush(힙, ㅇ)
    return [heapq.heappop(힙) for _ in range(len(힙))]

print(힙정렬([5, 2, 9, 1, 7, 3]))

# 넣을 때 (우선순위, 순번, 값) 으로 넣으면 같은 우선순위끼리 순서도 지켜집니다
할일 = []
for 순번, (급함, 이름) in enumerate([(2, "청소"), (1, "숙제"), (2, "설거지"), (1, "약속")]):
    heapq.heappush(할일, (급함, 순번, 이름))

while 할일:
    급함, _, 이름 = heapq.heappop(할일)
    print(f"[{급함}] {이름}")

🤔 확인 문제

힙(최소 힙)이 반드시 지키는 규칙은?

🤔 확인 문제

힙이 우선순위 큐에 알맞은 이유는?

🤔 확인 문제

10만 개 중 상위 5개만 필요할 때 가장 효율적인 방법은?