C-2: 힙·우선순위 큐 — "완전 이진트리를 배열 한 장에 담아, 가장 급한 걸 O(log n)에 꺼낸다"

안녕하세요! 코딩테스트와 CS의 길잡이, 홍순구 튜터입니다.

지난 시간엔 트리를 세웠습니다. 노드에 왼쪽·오른쪽 두 포인터를 달아 이진트리를 만들고, "왼쪽은 작게 오른쪽은 크게" 규칙을 건 이진탐색트리(BST)로 평균 O(log n) 탐색까지 왔죠. 그리고 마지막에 이런 걸 봤어요. BST에 값을 정렬된 순서로 넣으면 한쪽으로만 자라 일자가 되고, 탐색이 O(n)으로 무너진다고요. 트리의 높이가 곧 성능이라, 균형이 관건이었습니다.

오늘은 그 균형이 항상 보장되는 아주 특별한 트리를 다룹니다. 완전 이진트리(complete binary tree) — 위에서 아래로, 왼쪽에서 오른쪽으로 빈틈없이 채운 트리예요. 이 규칙적인 모양 덕분에 놀라운 일이 벌어집니다. 포인터를 하나도 쓰지 않고, 배열 한 장에 트리를 통째로 담을 수 있어요. 지난 시간 제가 "트리를 배열에 어떻게 담지?"를 상상해 보라고 했죠. 오늘 그 답을 봅니다.

이렇게 담은 트리에 규칙 하나("부모는 늘 자식보다 작다")를 걸면 힙(heap)이 됩니다. 힙은 가장 작은 값(또는 가장 큰 값)을 O(log n)에 꺼내 주는 그릇이에요. 그 위에 세운 게 우선순위 큐(priority queue)고요. 줄을 서긴 서는데, 먼저 온 순서가 아니라 "가장 급한 것"이 먼저 나오는 줄입니다.

 오늘의 여정 — "완전 이진트리를 배열 한 장에 담아, 가장 급한 걸 O(log n)에"

 [1] 우선순위 큐란 문제  →  매번 '가장 급한 것'을 꺼내야 한다면?
 [2] 배열 한 장에 트리   →  완전 이진트리 → 인덱스로 부모·자식을 오간다
 [3] 삽입 (sift up)     →  맨 끝에 넣고, 부모보다 작으면 위로 올린다
 [4] 삭제 (sift down)   →  루트를 빼고, 맨 끝을 올린 뒤 아래로 내린다
 [5] 실전은 heapq       →  직접 짠 원리를 C로 구현한 표준 라이브러리
 [6] 최대 힙 트릭        →  heapq는 최소 힙뿐 → -x 넣기·(우선순위, 값) 튜플
 [7] K번째 수 / Top-K   →  크기 K 힙을 유지해 O(n log k)
 [8] 여러 리스트 병합    →  우선순위 큐로 합치기 (+ 다익스트라 복선)

자, 트리를 배열에 담으러 가 봅시다. 출발합니다!

💡 오늘 수업의 핵심 — "완전 이진트리를 배열 하나에 담고, '부모 ≤ 자식' 규칙(힙 속성)을 sift up·sift down으로 지키며 최솟값을 O(log n)에 넣고 뺀다. 직접 구현으로 원리를 본 뒤, 실전에선 heapq로 최댓값/최솟값을 뽑고 K번째·병합 같은 유형을 푼다"

🎯 학습 목표

• 완전 이진트리를 배열 한 장으로 표현하고(부모 (i-1)//2·자식 2i+1/2i+2), 힙 속성을 sift up·sift down으로 지키며 힙을 직접 구현합니다(삽입·삭제 O(log n), 조회 O(1)).
• 힙이 왜 항상 O(log n)인지를 완전 이진트리의 높이(≈ log n)로 설명하고, 한쪽으로 치우치는 BST의 최악 O(n)과 대조합니다.
• 실전 코테에서 heapq로 최댓값/최솟값을 뽑고, 최대 힙 트릭(-x)·우선순위 튜플로 K번째 수·여러 리스트 병합 같은 빈출 유형을 풉니다.

Step 1: "매번 가장 급한 걸 먼저" — 우선순위 큐라는 문제

지난 시간까지 우리가 만든 큐(queue)를 떠올려 봅시다. 큐는 먼저 온 게 먼저 나가는(FIFO) 줄이었어요. 은행 번호표처럼, 순서대로 공평하게 처리하죠. 그런데 현실엔 순서보다 급함이 중요한 줄이 많습니다.

병원 응급실을 생각해 보세요. 접수한 순서가 아니라 위중한 환자부터 봅니다. 운영체제도 그래요. 여러 작업 중 우선순위가 높은 것부터 CPU를 줍니다. 이렇게 "들어온 순서와 무관하게, 매번 가장 급한(가장 크거나 가장 작은) 것을 꺼내는 줄"이 우선순위 큐(priority queue)입니다.

그럼 이걸 지금까지 배운 도구로 만들어 볼까요? 두 가지 방법이 바로 떠오릅니다.

 방법 A: 그냥 리스트에 담아 두고, 꺼낼 때마다 전체를 훑어 최솟값을 찾는다
   넣기   : 맨 끝에 append           → O(1)
   꺼내기 : 전부 훑어 최솟값 찾기      → O(n)   ← 꺼낼 때마다 매번 n번 스캔

 방법 B: 넣을 때마다 정렬된 상태를 유지한다
   넣기   : 자리를 찾아 끼우기         → O(n)   ← 넣을 때마다 밀어내기
   꺼내기 : 맨 앞(최솟값)을 뺀다        → O(1)

둘 다 한쪽 연산이 O(n)입니다. 원소가 10만 개인데 꺼내기를 10만 번 하면 100억 번 연산이라, "1초에 약 1억 번" 잣대로 100초. 시간 초과예요. 넣기도 꺼내기도 자주 일어나는데 어느 한쪽이 O(n)이면 감당이 안 됩니다.

우리가 원하는 건 넣기도 꺼내기도 O(log n)입니다. 그래야 10만 번 반복해도 100000 × 17 ≈ 170만 번이라 가뿐하죠(log₂ 100000 ≈ 17). 이걸 해내는 자료구조가 바로 힙입니다. 완전 정렬까지는 필요 없어요. "가장 급한 것 하나만 빠르게"가 핵심이니까요.

🎯 코테에서는 "매번 최댓값/최솟값을 꺼내며 처리"하는 문제가 우선순위 큐 신호입니다. 작업을 우선순위로 처리하거나(프로그래머스 "더 맵게"), 가장 가까운 것부터 확장하는(다익스트라 최단 경로) 유형이 전부 힙으로 풀립니다. "정렬을 매번 다시 하고 있다"는 생각이 들면 힙을 의심하세요.

💡 한 줄 정리

우선순위 큐는 "들어온 순서와 무관하게 매번 가장 급한(최대/최소) 것을 꺼내는 줄"이다. 리스트로 흉내 내면 넣기나 꺼내기 중 한쪽이 O(n)으로 느려, 넣기·꺼내기 모두 O(log n)에 해내는 힙이 필요하다.

Step 2: 완전 이진트리를 배열 한 장에

힙의 바탕은 완전 이진트리(complete binary tree)입니다. 정의는 단순해요. 마지막 레벨을 빼면 모든 레벨이 꽉 차 있고, 마지막 레벨은 왼쪽부터 빈틈없이 채워진 이진트리입니다. 중간에 구멍을 내지 않고 왼쪽에서 오른쪽으로, 위에서 아래로 순서대로 채워 나간 모양이죠.

이 "빈틈없이 순서대로"라는 규칙이 마법을 부립니다. 노드에 번호를 위에서 아래로, 왼쪽에서 오른쪽으로 0, 1, 2, … 매기면, 그 번호가 그대로 배열의 인덱스가 돼요. 포인터가 필요 없습니다.

 완전 이진트리                          배열 한 장

          (1)                    index:  0   1   2   3   4   5   6
        /     \                   값:    1   3   7   5   4   8   9
      (3)     (7)
      / \     / \
    (5) (4) (8) (9)

  트리의 부모-자식 관계가 '인덱스 계산'으로 바뀐다:
    index i 의 부모       = (i - 1) // 2
    index i 의 왼쪽 자식   = 2 * i + 1
    index i 의 오른쪽 자식 = 2 * i + 2

확인해 볼까요. 인덱스 1(값 3)의 자식은 2*1+1=3(값 5)과 2*1+2=4(값 4)입니다. 그림에서 3의 자식이 5·4가 맞죠. 거꾸로 인덱스 4(값 4)의 부모는 (4-1)//2=1(값 3)이고요. 트리를 오르내리는 게 포인터 추적이 아니라 산수 한 번으로 끝납니다.

왜 이게 되냐면, 완전 이진트리는 중간에 빈 자리가 없어 배열에 구멍 없이 딱 들어차기 때문이에요. BST처럼 한쪽으로 치우칠 수가 없습니다. 만약 치우치면 배열 중간에 빈칸이 생겨 "완전"이 깨지니까요. 그래서 완전 이진트리의 높이는 항상 약 log₂ n입니다. 노드가 n개면 높이가 log n으로 눌려요. 이 점이 뒤에서 "힙은 왜 항상 O(log n)인가"의 뿌리가 됩니다.

코드로는 정말 리스트 하나가 전부입니다.

# structures/heap.py
class MinHeap:
    def __init__(self):
        self.data = []          # 완전 이진트리를 담은 배열 한 장

    def peek(self):
        """가장 작은 값(루트)을 꺼내지 않고 들여다본다. O(1)."""
        if not self.data:
            raise IndexError("peek from empty heap")
        return self.data[0]

여기에 "부모는 늘 자식보다 작다"는 힙 속성(heap property)을 걸면 최소 힙이 됩니다. 위 그림이 딱 그래요. 1 ≤ 3·7, 3 ≤ 5·4, 7 ≤ 8·9. 모든 부모가 자식보다 작죠. 이 속성 덕분에 가장 작은 값은 언제나 루트, 즉 배열의 0번 자리에 있습니다. 그래서 peek(최솟값 조회)는 self.data[0] 한 줄로 O(1)이에요.

한 가지 짚고 갈 점. 힙 속성은 "부모 < 자식"만 요구할 뿐, 형제끼리의 순서나 좌우 대소는 강제하지 않습니다. 위 그림에서 3의 자식이 5·4인데 왼쪽(5)이 오른쪽(4)보다 크죠. BST와 다른 대목이에요. BST는 "왼쪽 < 나 < 오른쪽"으로 좌우까지 줄 세웠지만, 힙은 오직 "위아래"만 봅니다. 그래서 힙은 정렬된 구조가 아니에요. "최솟값이 맨 위"라는 것만 보장합니다.

🎯 코테에서는 힙을 배열로 표현하는 이 인덱스 공식(2i+1·2i+2·(i-1)//2)이 힙 정렬이나 세그먼트 트리 같은 "배열로 트리 흉내" 유형의 바탕이 됩니다. 실전에선 heapq가 이 배열을 알아서 관리하지만, 원리를 알아야 "왜 힙 인덱스가 이렇게 도나"가 보여요.

💡 한 줄 정리

완전 이진트리는 빈틈없이 채워져 높이가 항상 약 log n이라, 포인터 없이 배열 한 장에 담긴다. 인덱스 i의 부모는 (i-1)//2, 자식은 2i+1·2i+2. 여기에 "부모 ≤ 자식"(힙 속성)을 걸면 최솟값이 늘 0번 자리에 와 조회가 O(1)이다.

Step 3: 삽입 — 끝에 넣고 위로 올리기(sift up)

이제 힙에 값을 넣어 봅시다. 힙은 두 가지를 동시에 지켜야 해요. (1) 완전 이진트리 모양(빈틈없이), (2) 힙 속성(부모 ≤ 자식). 새 값을 어디에 넣어야 이 둘이 안 깨질까요?

모양부터 지키려면 새 값은 배열의 맨 끝, 즉 트리의 맨 마지막 칸에 와야 합니다. 그래야 빈틈이 안 생겨요. 그런데 그 칸의 부모가 새 값보다 클 수 있죠. 그럼 힙 속성이 깨집니다. 이때 부모와 서로 바꿔 위로 올리는 걸 반복해요. 이걸 sift up(위로 밀어 올리기)이라고 합니다.

값 1을 [3, 5, 8] 힙에 넣는 과정을 따라가 봅시다.

 push(1): 맨 끝에 1을 붙인다
   [3, 5, 8, 1]
             └ 1의 부모는 (3-1)//2=1 → 값 5. 5 > 1 이라 힙 속성 위반 → 위로

   [3, 1, 8, 5]      (1 ↔ 5 자리 교환)
        └ 1의 부모는 (1-1)//2=0 → 값 3. 3 > 1 이라 또 위반 → 위로

   [1, 3, 8, 5]      (1 ↔ 3 자리 교환) → 루트에 도착, 멈춤

새 값 1이 부모보다 작은 동안 계속 위로 올라가, 결국 루트에 자리 잡았습니다. 부모보다 크거나 같아지면(또는 루트에 닿으면) 멈춰요. 올라간 거리는 아무리 길어야 트리의 높이, 즉 log n입니다. 그래서 삽입은 O(log n)이에요.

# structures/heap.py — MinHeap 클래스 안(__init__·peek는 Step 2에서 봤어요)
class MinHeap:
    def push(self, value):
        self.data.append(value)
        self._sift_up(len(self.data) - 1)

    def _sift_up(self, i):
        """i번 값을 부모보다 작지 않을 때까지 위로 밀어 올린다. O(log n)."""
        while i > 0:
            parent = (i - 1) // 2
            if self.data[i] < self.data[parent]:
                self.data[i], self.data[parent] = self.data[parent], self.data[i]
                i = parent
            else:
                break                   # 부모가 나보다 작거나 같으면 제자리

push는 맨 끝에 붙이고 그 인덱스에서 _sift_up을 부릅니다. _sift_up은 부모보다 작으면 교환하고 부모 자리로 올라가고, 아니면 멈춰요. 파이썬의 a, b = b, a 한 줄 교환이 자리 바꾸기입니다.

실제로 [5, 3, 8, 1]을 차례로 넣으면 배열이 이렇게 변해요. push(5) → [5], push(3) → [3, 5], push(8) → [3, 5, 8], push(1) → [1, 3, 8, 5]. 마지막에 넣은 1이 sift up으로 루트까지 올라간 게 보이죠.

🎯 코테에서는 삽입이 O(log n)이라, n개를 하나씩 넣어 힙을 만들면 O(n log n)입니다. "값을 계속 추가하며 그때그때 최솟값이 필요한" 스트림 처리에 이 삽입이 쓰여요. (배열이 통째로 주어졌을 땐 더 빠른 O(n) 방법이 따로 있는데, Step 5에서 봅니다.)

💡 한 줄 정리

삽입은 새 값을 배열 맨 끝(완전 이진트리의 마지막 자리)에 붙인 뒤, 부모보다 작으면 부모와 교환하며 위로 올린다(sift up). 올라가는 거리가 트리 높이라 O(log n)이다.

Step 4: 삭제 — 루트 빼고 아래로 내리기(sift down)

우선순위 큐의 진짜 목적은 "가장 급한 것 꺼내기"입니다. 최소 힙에서 그건 루트(최솟값)를 빼는 일이에요. 그런데 루트를 그냥 빼 버리면 트리 꼭대기에 구멍이 납니다. 이 구멍을 어떻게 메울까요?

여기서도 모양을 먼저 지킵니다. 맨 끝 값을 루트 자리로 옮겨요. 그럼 빈틈은 사라지지만, 이번엔 그 값이 자식들보다 클 수 있어 힙 속성이 깨지죠. 그래서 두 자식 중 더 작은 쪽과 교환하며 아래로 내려갑니다. 이걸 sift down(아래로 밀어 내리기)이라고 해요.

[1, 3, 7, 5, 4, 8, 9] 힙에서 최솟값 1을 빼는 과정입니다.

 pop(): 루트(1)를 빼고, 맨 끝 값(9)을 루트 자리로 올린다
   [9, 3, 7, 5, 4, 8]
    └ 9의 두 자식은 3·7. 더 작은 3보다 크다 → 3과 교환하며 아래로

   [3, 9, 7, 5, 4, 8]      (9 ↔ 3 교환)
       └ 9의 두 자식은 5·4. 더 작은 4보다 크다 → 4와 교환하며 아래로

   [3, 4, 7, 5, 9, 8]      (9 ↔ 4 교환) → 더 내려갈 자식 없음, 멈춤

루트에 올라온 9가 "더 작은 자식"과 교환하며 제자리를 찾아 내려갔어요. 왜 더 작은 쪽과 바꿔야 할까요? 부모 자리에는 두 자식보다 작은 값이 와야 힙 속성이 맞기 때문이에요. 둘 중 작은 값을 올려야 그 값이 두 형제보다 작음이 보장됩니다. 내려간 거리도 최대 트리 높이라 삭제 역시 O(log n)입니다.

# structures/heap.py — 이어서 MinHeap 클래스 안
class MinHeap:
    def pop(self):
        if not self.data:
            raise IndexError("pop from empty heap")
        root = self.data[0]
        last = self.data.pop()          # 맨 끝 값을 뽑아
        if self.data:                   # 아직 남아 있으면 루트에 올리고 내린다
            self.data[0] = last
            self._sift_down(0)
        return root

    def _sift_down(self, i):
        """i번 값을 두 자식보다 크지 않을 때까지 아래로 밀어 내린다. O(log n)."""
        n = len(self.data)
        while True:
            left = 2 * i + 1
            right = 2 * i + 2
            smallest = i
            if left < n and self.data[left] < self.data[smallest]:
                smallest = left
            if right < n and self.data[right] < self.data[smallest]:
                smallest = right
            if smallest == i:           # 두 자식보다 작거나 같으면 제자리
                break
            self.data[i], self.data[smallest] = self.data[smallest], self.data[i]
            i = smallest

_sift_down은 나와 두 자식 중 가장 작은 값을 찾아, 그게 내가 아니면 교환하고 그 자리로 내려갑니다. 자식이 배열 범위(n)를 벗어나면 없는 것이니 left < n 같은 경계 검사를 넣었어요. 내가 이미 제일 작으면(smallest == i) 멈춥니다.

여기까지 오면 힙의 세 연산 빅오가 한 표로 정리됩니다.

 연산            시간        하는 일
 ─────────────────────────────────────────────────────
 peek (조회)     O(1)        루트(0번)를 그냥 본다
 push (삽입)     O(log n)    맨 끝에 넣고 sift up
 pop  (삭제)     O(log n)    루트 빼고 맨 끝을 올린 뒤 sift down
 ─────────────────────────────────────────────────────
 공간            O(n)        원소 n개를 배열에 담는다

여기서 살짝 맛만 보고 갈 게 있어요. 힙에 n개를 다 넣은 뒤 하나씩 pop하면, 최솟값부터 순서대로 나옵니다. 즉 정렬이 돼요. [5, 3, 8, 1, 4, 7, 9]를 넣고 전부 꺼내면 [1, 3, 4, 5, 7, 8, 9]가 나오죠. 넣기 n번(각 O(log n)) + 꺼내기 n번(각 O(log n))이라 O(n log n)에 정렬됩니다. 이게 힙 정렬(heap sort)인데, 정렬은 다음 카테고리(D)에서 본격적으로 다뤄요. 오늘은 "힙으로 정렬도 되는구나" 정도만.

🎯 코테에서는 pop으로 매번 최솟값을 뽑아 처리하는 게 우선순위 큐의 핵심 동작입니다. "가장 작은(또는 큰) 것부터 하나씩 처리"하는 그리디·최단 경로 유형이 전부 이 pop 위에서 돕니다.

💡 한 줄 정리

삭제는 루트(최솟값)를 빼고 맨 끝 값을 루트로 올린 뒤, 두 자식 중 더 작은 쪽과 교환하며 아래로 내린다(sift down). 내려가는 거리가 트리 높이라 O(log n)이다. peek O(1)·push O(log n)·pop O(log n)이 힙의 세 연산이다.

Step 5: 실전은 heapq — 직접 구현 vs 내장

여기까지 힙을 손으로 짜며 원리를 봤습니다. 완전 이진트리, 배열 표현, sift up·down, O(log n). 이제 두 트랙 중 실전 트랙이에요. 코딩테스트에서 힙이 필요하면 우리는 MinHeap을 직접 짜지 않습니다. 파이썬 표준 라이브러리 heapq를 써요.

heapq는 우리가 짠 것과 원리가 똑같습니다. 다만 C로 구현돼 더 빠르고, 오래 검증돼 버그가 없어요. 한 가지 특이한 점은 heapq가 별도 힙 클래스를 주지 않는다는 겁니다. 그냥 평범한 파이썬 리스트를 힙으로 다루는 함수들을 줘요.

import heapq

heap = []
heapq.heappush(heap, 5)         # 삽입 O(log n)
heapq.heappush(heap, 1)
heapq.heappush(heap, 3)
print(heap[0])                  # 1 — 최솟값은 늘 0번(peek O(1))
print(heapq.heappop(heap))      # 1 — 최솟값 삭제 O(log n)

heappush(heap, x)가 우리의 push, heappop(heap)이 우리의 pop이에요. 최솟값 조회는 heap[0](리스트 0번)으로 그냥 봅니다. 우리가 직접 짠 sift up·down을 heapq가 안에서 똑같이 돌리는 거죠.

배열이 통째로 있으면 heapify로 제자리에서 O(n)에 힙으로 만듭니다(방금 🙋에서 본 그 O(n) 방법이에요).

data = [5, 3, 8, 1, 4, 7, 9]
heapq.heapify(data)             # 제자리에서 O(n)에 힙으로
print(data[0])                  # 1 — 이제 최솟값이 맨 앞

여기서 두 트랙의 판단 기준을 정리해 둡시다.

 직접 구현(structures/heap.py)  vs   내장(heapq)

 직접 구현을 왜 배우나
   - 면접에서 "힙 어떻게 도나요"를 물으면 sift up·down으로 답한다
   - heapq에 없는 변형(커스텀 동작)이 필요할 때 원리가 밑천이 된다
   - "왜 O(log n)인가"를 배열·높이로 설명할 수 있다

 실전은 왜 heapq인가
   - C로 짜여 더 빠르고, 버그가 없다(직접 짜면 sift down 실수가 잦다)
   - heappush·heappop·heapify·nlargest 등 필요한 게 다 있다
   - 코드가 짧아 실수가 준다

원리를 아는 사람이 라이브러리를 신뢰할지 의심할지 판단합니다. 우리는 힙이 안에서 뭘 하는지 봤으니, 이제 heapq를 믿고 씁니다. 다만 heapq에는 큰 함정이 하나 있어요. 다음 Step에서 그걸 넘습니다.

🎯 코테에서는 파이썬으로 힙 문제를 풀 때 import heapq가 사실상 표준입니다. heappush·heappop·heapify 세 개면 대부분 풀려요. 직접 구현은 원리 이해와 면접 답변용이고, 문제 풀이의 손은 heapq로 갑니다.

💡 한 줄 정리

실전에선 힙을 직접 짜지 않고 heapq를 쓴다. 평범한 리스트에 heappush(삽입)·heappop(삭제)·heapify(O(n) 빌드)를 적용하며, 최솟값은 heap[0]으로 본다. 직접 구현은 원리·면접·변형용, heapq는 C로 짜여 빠르고 안전한 실전용이다.

Step 6: 최대 힙 트릭 + 우선순위 튜플

heapq의 함정은 이겁니다. heapq는 최소 힙만 제공해요. 최댓값을 빠르게 뽑는 최대 힙(max heap) 함수가 따로 없습니다. 그런데 코테엔 "가장 큰 것부터"가 수두룩하죠. 어떻게 할까요?

답은 부호를 뒤집는 트릭입니다. 값을 넣을 때 -x로 넣고, 꺼낼 때 다시 -를 붙여 되돌려요. 최소 힙이 -x 중 가장 작은 걸 주면, 그게 원래 값 중 가장 큰 것이거든요.

import heapq

nums = [3, 1, 4, 1, 5]
max_heap = [-x for x in nums]   # 부호를 뒤집어 넣는다
heapq.heapify(max_heap)
largest = -heapq.heappop(max_heap)      # 꺼낼 때 부호를 되돌린다
print(largest)                  # 5 — 최댓값

-x로 넣으니 -5가 가장 작아 맨 위에 오고, 꺼내 -를 붙이면 5. 최소 힙으로 최대 힙을 흉내 낸 거예요. 코테에서 아주 자주 쓰는 관용구라 익혀 두세요.

또 하나 중요한 패턴. 힙에 튜플을 넣으면 첫 번째 원소를 우선순위로 삼아 정렬됩니다. (우선순위, 값) 꼴로 넣으면, 우선순위가 가장 작은 것부터 나와요.

pq = []
heapq.heappush(pq, (2, "b"))
heapq.heappush(pq, (1, "a"))
heapq.heappush(pq, (3, "c"))
print(heapq.heappop(pq))        # (1, 'a') — 우선순위 1이 가장 급하다

우선순위 1인 (1, "a")가 먼저 나왔죠. 값 자체와 우선순위가 다를 때 이 튜플 방식이 필수예요. 예를 들어 다익스트라에서 "현재까지 거리"를 우선순위로, "노드 번호"를 값으로 묶어 (거리, 노드)로 넣습니다. 파이썬은 튜플을 앞에서부터 순서대로 비교하니, 첫 원소가 같으면 두 번째로 넘어가요.

 최대 힙 트릭 요약

  최댓값을 뽑고 싶다     →  -x 로 넣고, 꺼낼 때 -(다시 뒤집기)
  우선순위가 값과 다르다  →  (우선순위, 값) 튜플로 넣기
  튜플 비교              →  앞 원소부터 차례로 (첫 원소가 우선순위)

🎯 코테에서는 "가장 큰 것부터"는 -x 트릭, "우선순위와 데이터가 따로"는 (우선순위, 값) 튜플 — 이 둘이 힙 문제의 90%를 커버합니다. 특히 다익스트라·작업 스케줄링에서 (비용, 대상) 튜플이 단골이에요.

💡 한 줄 정리

heapq는 최소 힙만 주므로, 최댓값이 필요하면 -x로 넣고 꺼낼 때 부호를 되돌린다. 우선순위와 값이 다를 땐 (우선순위, 값) 튜플을 넣어 첫 원소로 정렬시킨다. 이 두 트릭이 힙 코테의 핵심 관용구다.

Step 7: 활용 ① — K번째 수 / Top-K

이제 힙으로 실제 유형을 풀어 봅시다. 첫 번째는 "가장 큰(작은) K개" 또는 "K번째로 큰(작은) 수"입니다. 코테 단골이에요.

n개 중 K번째로 큰 수를 찾는다고 해 봅시다. 가장 단순한 건 전부 정렬해 뒤에서 K번째를 보는 거예요. O(n log n)입니다. 그런데 n이 아주 크고 K가 작으면(예: 100만 개 중 5번째) 아깝죠. 전체를 줄 세울 필요가 없으니까요.

힙으로 하면 크기 K짜리 최소 힙 하나만 유지하면 됩니다. "지금까지 본 가장 큰 K개"를 힙에 담아 두는 거예요. 그러면 그 힙의 루트(최솟값)가 곧 K번째로 큰 수입니다.

# structures/exercises_c2.py
import heapq

def kth_largest(nums, k):
    heap = []
    for x in nums:
        if len(heap) < k:
            heapq.heappush(heap, x)
        elif x > heap[0]:
            heapq.heappushpop(heap, x)      # 더 큰 값이 오면 가장 작은 걸 밀어낸다
    return heap[0]

힙에 K개가 안 찼으면 그냥 넣고, 다 찼으면 새 값이 힙의 최솟값(heap[0])보다 클 때만 교체합니다. heappushpop(heap, x)는 x를 넣고 최솟값을 빼는 걸 한 번에 하는 함수예요(따로 push·pop보다 효율적). 이러면 힙엔 늘 "가장 큰 K개"만 남고, 그 최솟값이 답입니다.

빅오를 따져 볼까요. 원소 n개를 한 번씩 보며, 각 단계에서 크기 K 힙에 push/pop(O(log K))을 해요. 그래서 시간 O(n log K)·공간 O(K)입니다. K가 n보다 훨씬 작으면 전체 정렬 O(n log n)보다 빨라요.

[3, 2, 1, 5, 6, 4]에서 2번째로 큰 수를 찾으면 5가 나옵니다. 큰 값 6·5를 힙에 남기고, 그 최솟값 5가 2번째로 큰 수죠.

실전에선 heapq가 이 패턴을 함수로도 줍니다. nlargest·nsmallest예요.

import heapq

data = [3, 1, 4, 1, 5, 9, 2, 6]
print(heapq.nlargest(3, data))      # [9, 6, 5] — 큰 것 3개
print(heapq.nsmallest(3, data))     # [1, 1, 2] — 작은 것 3개

nlargest(k, data)는 방금 우리가 짠 "크기 K 힙 유지"를 안에서 그대로 해요. K가 작으면 이게 정렬보다 빠릅니다. 단 K가 n에 가까우면 그냥 sorted가 나을 수 있으니, "일부만 필요할 때" 쓰는 도구로 기억하세요.

🎯 코테에서는 "K번째로 큰/작은 수"(LeetCode Kth Largest Element), "가장 가까운 K개"(K Closest Points) 유형이 이 크기 K 힙 패턴입니다. nlargest/nsmallest로 짧게 풀거나, 스트림이면 직접 크기 K 힙을 유지해요.

💡 한 줄 정리

K번째로 큰 수는 크기 K짜리 최소 힙을 유지해 그 루트로 O(n log K)에 구한다(전체 정렬 O(n log n)보다 K가 작을 때 빠름). 실전에선 heapq.nlargest·nsmallest로 짧게 쓴다.

Step 8: 활용 ② — 여러 리스트 병합 + 다음으로 가는 다리

마지막 유형은 "이미 정렬된 여러 리스트를 하나의 정렬된 리스트로 합치기"입니다. 이것도 힙이 깔끔하게 풀어요.

정렬된 리스트가 세 개 있다고 합시다. [1, 4, 7], [2, 5], [3, 6, 8]. 이걸 전부 합쳐 정렬하려면, 매 순간 "세 리스트의 맨 앞 중 가장 작은 것"을 골라 빼면 됩니다. "여러 후보 중 최솟값을 반복해 꺼낸다" — 딱 우선순위 큐죠.

각 리스트의 맨 앞을 힙에 넣어 두고, 최솟값을 꺼낸 뒤 그 리스트의 다음 값을 힙에 채워 넣기를 반복해요. 힙에는 항상 리스트 개수(k)만큼만 들어 있으니, 원소가 총 N개면 시간 O(N log k)입니다. 파이썬은 이걸 heapq.merge로 바로 줘요.

import heapq

a = [1, 4, 7]
b = [2, 5]
c = [3, 6, 8]
print(list(heapq.merge(a, b, c)))       # [1, 2, 3, 4, 5, 6, 7, 8]

세 리스트가 하나의 정렬된 흐름으로 합쳐졌습니다. 이 "여러 정렬된 갈래를 힙으로 합친다"는 아이디어는 병합 정렬(다음 카테고리 D-1)이나 대용량 외부 정렬에서 다시 만나요.

여기서 잠깐 오늘을 넘어 앞을 봅시다. 방금 Step 6에서 (우선순위, 값) 튜플로 "우선순위가 가장 낮은(급한) 것"을 꺼냈고, Step 7·8에선 힙으로 "매번 최선의 후보"를 골랐어요. 이 "매번 가장 가까운(싼) 후보를 꺼내 확장한다"가 바로 최단 경로 알고리즘 다익스트라(Dijkstra)의 심장입니다. 지도에서 출발지부터 "지금까지 가장 가까운 곳"을 우선순위 큐로 계속 꺼내며 뻗어 나가죠.

 오늘의 힙이 어디로 이어지나

  힙 (C-2)  ──▶  다익스트라 최단 경로 (F-1)   "가장 가까운 후보를 큐에서 꺼내 확장"
            ──▶  힙 정렬 (D-1)               "전부 넣고 하나씩 빼면 정렬"
            ──▶  그래프 (C-3, 바로 다음)       "노드를 더 자유롭게 잇는 구조로"

다익스트라는 아직 멀었어요(그래프와 여러 알고리즘을 배운 뒤 F-1에서 만납니다). 오늘은 "우선순위 큐가 그 바탕에 깔린다"만 심어 둡니다. 힙을 손에 넣었다는 건 나중에 다익스트라를 만났을 때 절반은 이미 아는 상태라는 뜻이에요.

🎯 코테에서는 "정렬된 K개 리스트 병합"(LeetCode Merge k Sorted Lists)이 이 힙 병합의 대표 문제입니다. 그리고 오늘 배운 우선순위 큐는 다익스트라·프림(최소 신장 트리) 같은 고급 그래프 알고리즘에서 다시 주인공이 돼요.

💡 한 줄 정리

정렬된 여러 리스트 병합은 "각 리스트 맨 앞 중 최솟값을 반복해 꺼내는" 우선순위 큐 문제라, heapq.merge로 O(N log k)에 합친다. 이 "매번 최선의 후보를 꺼내 확장"이 다익스트라 최단 경로(F-1)의 심장으로 이어진다.

마무리

오늘은 트리를 배열 한 장에 담아 "가장 급한 것"을 O(log n)에 꺼내는 힙을 만들었습니다. 완전 이진트리라 높이가 늘 log n이고, sift up·down으로 힙 속성을 지키며 넣고 뺐어요. 지난 시간 BST가 치우쳐 O(n)으로 무너질 수 있던 것과 달리, 힙은 모양 자체가 균형을 강제해 최악에도 O(log n)을 지킵니다.

오늘 배운 핵심 세 가지

• 💡 하나 — 완전 이진트리는 배열 한 장에 담긴다. 인덱스 i의 부모는 (i-1)//2, 자식은 2i+1·2i+2. 빈틈없이 채워져 높이가 항상 약 log n이라, 포인터 없이 산수만으로 트리를 오르내린다.
• 💡 둘 — 힙은 "부모 ≤ 자식"만 지키며 최솟값을 O(log n)에 넣고 뺀다. 삽입은 맨 끝에 넣고 sift up, 삭제는 루트를 빼고 맨 끝을 올린 뒤 sift down. 조회(peek)는 O(1). 완전 이진트리라 BST와 달리 최악에도 O(log n)이 보장된다.
• 💡 셋 — 실전은 heapq, 최대 힙은 -x 트릭. 직접 구현으로 원리를 보고, 코테에선 heappush·heappop·heapify를 쓴다. heapq는 최소 힙뿐이라 최댓값은 -x로, 우선순위가 값과 다르면 (우선순위, 값) 튜플로 넣는다.

다음 시간 예고

다음 시간엔 비선형 자료구조의 마지막, 그래프(graph)로 갑니다. 트리는 사실 "사이클 없이 연결된 특수한 그래프"라고 지난 시간 말했죠. 그 제약을 풀면 그래프예요. 노드(정점)를 자유롭게 잇는 간선으로, 친구 관계나 도시 간 도로처럼 얽힌 구조를 표현합니다. 이걸 컴퓨터에 어떻게 담을지 — 인접 행렬과 인접 리스트라는 두 방법을 메모리·시간 트레이드오프로 견줘 봐요. 그리고 오늘의 힙과 다음 시간의 그래프가 만나면, 나중에 다익스트라 최단 경로가 됩니다. 오늘 "우선순위 큐로 가장 가까운 것부터 꺼낸다"를 기억해 두세요.

과제

오늘 배운 힙을 직접 손으로 다뤄 보는 문제들입니다. 풀어 본 뒤 예시 답안과 맞춰 보세요. 실전 코테 방식대로 heapq를 써도 좋고, 각 풀이의 시간·공간 복잡도를 빅오로 적는 것도 잊지 마세요.

[기초] 더 맵게 — 스코빌 지수 섞기

모든 음식의 스코빌 지수를 K 이상으로 만들려고 합니다. 가장 안 매운 음식 두 개를 섞어 새 음식을 만드는데, 새 스코빌 지수는 가장 안 매운 음식 + 두 번째로 안 매운 음식 × 2입니다. 모든 음식이 K 이상이 될 때까지 반복할 때, 필요한 최소 섞기 횟수를 구하세요. 아무리 섞어도 K 이상으로 못 만들면 -1을 반환합니다.

예를 들어 [1, 2, 3, 9, 10, 12], K=7이면 답은 2입니다. 매번 "가장 작은 값"과 "두 번째로 작은 값"이 필요하죠. 무엇을 쓰면 이 둘을 O(log n)에 꺼낼 수 있을지 생각해 보세요. 다 섞어 하나만 남았는데도 K 미만이면 불가능이라는 경계도 챙기고요. 시간·공간 복잡도를 빅오로 적으세요. (프로그래머스 "더 맵게" 유형입니다.)

[응용] K번째로 큰 수

정수 배열 nums와 정수 k가 주어질 때, k번째로 큰 수를 반환하는 함수를 작성하세요. 예를 들어 [3, 2, 1, 5, 6, 4], k=2면 2번째로 큰 수인 5입니다.

전부 정렬하면 O(n log n)이지만, 오늘 Step 7에서 본 "크기 K 힙 유지"로 O(n log K)에 풀 수 있어요. 핵심 질문 하나. k번째로 큰 수를 구하는데 왜 최소 힙을 쓸까요? "유지할 K개의 커트라인"이 무엇인지 떠올리면 답이 보입니다. 크기 K 힙을 유지하며 새 값이 커트라인보다 클 때만 교체해 보세요. 시간·공간 복잡도를 빅오로 적으세요. (LeetCode "Kth Largest Element in an Array" 패턴입니다.)

[심화] 스트림에서 중앙값 구하기

숫자가 하나씩 흘러 들어올 때, 그때까지 들어온 수들의 중앙값(median)을 매번 구하는 자료구조를 설계하세요. add(num)으로 수를 넣고, median()으로 지금까지의 중앙값을 반환합니다. 개수가 홀수면 가운데 값, 짝수면 가운데 두 값의 평균이에요.

예를 들어 1, 2, 3을 차례로 넣으면 중앙값은 1 → 1.5 → 2로 바뀝니다. 매번 전부 정렬하면 O(n log n)이라 느려요. 힌트는 힙 두 개입니다. 작은 절반과 큰 절반을 각각 힙으로 나눠 가지면, 두 힙의 경계가 곧 중앙이 되죠. 작은 절반은 최대 힙(오늘 배운 -x 트릭!), 큰 절반은 최소 힙으로 두고, 두 힙의 크기 차를 1 이하로 맞춰 보세요. add가 O(log n), median이 O(1)이면 성공입니다. 시간·공간 복잡도를 빅오로 적으세요. (LeetCode "Find Median from Data Stream" 패턴 — 힙 두 개를 다루는 대표 문제입니다.)

생각해볼 주제

정답이 하나가 아닌 질문들입니다. 혼자 고민해도 좋고, 스터디에서 토론해도 좋아요.

1. 힙은 왜 BST와 달리 "최악에도 O(log n)"일까?

지난 시간 BST는 값을 정렬된 순서로 넣으면 한쪽으로 치우쳐 최악 O(n)으로 무너졌습니다. 그래서 삽입·탐색에 "평균 O(log n)·최악 O(n)"을 함께 적었죠. 그런데 오늘 힙은 최악에도 O(log n)이라고 했습니다. 무엇이 이 차이를 만들까요? 힌트는 "완전 이진트리"라는 모양의 제약입니다. 힙은 왜 한쪽으로 치우칠 수가 없는지, 그 대가로 힙이 포기한 것(BST는 되는데 힙은 안 되는 것)은 무엇인지 생각해 보세요. "탐색"을 힙에서 하려면 어떻게 되는지 따져 보면 그 대가가 선명해집니다.

2. 완전 정렬이 필요 없을 때, 정렬 대신 힙을 언제 고를까?

"가장 큰 5개"를 구하는데 데이터가 100만 개라고 합시다. 전부 정렬(O(n log n))하면 5개 빼고 다 버릴 정보까지 줄 세우는 셈이에요. 힙으로 크기 5를 유지하면 O(n log 5) ≈ O(n)이고요. 반대로 "전부 정렬된 결과가 필요"하거나 "K가 n에 가까우면" 그냥 정렬이 낫습니다. 어떤 신호를 보고 "정렬 말고 힙"을 판단할지 정리해 보세요. heapq.nlargest와 sorted(...)[:k]의 경계가 대략 어디쯤일지, "필요한 게 전체 순서인가 vs 상위 몇 개인가"를 기준으로 생각해 보면 좋습니다.

3. 직접 구현 vs heapq — 언제 손으로 짜고 언제 라이브러리를 쓸까?

오늘 힙을 배열로 직접 구현했지만, 실전에선 heapq를 쓴다고 했습니다. 두 트랙을 모두 둔 이유가 있어요. 면접에서 "힙이 어떻게 O(log n)인가"를 물으면 sift up·down으로 답해야 하고, heapq에 없는 변형(예: 임의 원소를 힙에서 삭제·값 갱신)이 필요하면 원리를 알아야 손댈 수 있죠. 반대로 평범한 문제 풀이에선 C로 짜여 빠르고 버그 없는 heapq가 답이고요. "직접 구현으로 원리, 내장으로 실전"이라는 이 과목의 두 트랙이, 지난 시간 해시·트리부터 오늘 힙까지 어떻게 반복되는지 돌아보세요. 원리를 아는 사람이 라이브러리를 언제 믿고 언제 의심할지 판단한다는 게 무슨 뜻일지도요.