C_05_Heap

Heap (힙)

목차

1. 개념 및 정의
2. 힙의 종류
3. 힙의 구조
4. Python heapq 모듈
5. 최대 힙 구현
6. 우선순위 큐
7. 구현 코드
8. 실전 문제
9. 힙 문제 유형 정리
10. 시간복잡도

---

1. 개념 및 정의

1.1 힙이란?

힙(Heap)은 완전 이진 트리 기반의 자료구조로, 트리에서 최대/최소값을 빠르게 구하기 위해 사용됩니다.

힙 = 우선순위 큐를 구현하기 위한 완전 이진 트리

1.2 힙의 특징

• 완전 이진 트리: 마지막 레벨을 제외한 모든 레벨이 채워져 있고, 마지막 레벨은 왼쪽부터 채워짐
• 힙 속성: 부모와 자식 사이에 대소 관계 유지
• 최대/최소값 접근: O(1)
• 삽입/삭제: O(log n)

1.3 일상 속 힙의 예

예시	설명
응급실 대기	가장 위급한 환자가 먼저 치료
작업 스케줄링	우선순위 높은 작업부터 처리
네트워크 패킷	중요도에 따라 패킷 처리
게임 AI	가장 위협적인 적을 먼저 공격

1.4 힙 vs 이진 탐색 트리

특성	힙 (Heap)	BST (이진 탐색 트리)
목적	최대/최소 빠른 접근	정렬된 데이터 유지
정렬	부모 > 자식 (또는 <)	왼쪽 < 부모 < 오른쪽
구조	완전 이진 트리	이진 트리
최대/최소 접근	O(1)	O(log n) ~ O(n)
탐색	O(n)	O(log n) 평균

---

2. 힙의 종류

2.1 최대 힙 (Max Heap)

최대 힙: 부모 노드 ≥ 자식 노드

             100
            /    \
          90      80
         /  \    /  \
        70  60  50  40

특징:
- 루트가 최대값
- 부모는 항상 자식보다 크거나 같음
- 형제 사이에는 대소 관계 없음

2.2 최소 힙 (Min Heap)

최소 힙: 부모 노드 ≤ 자식 노드

              10
            /    \
          20      30
         /  \    /  \
        40  50  60  70

특징:
- 루트가 최소값
- 부모는 항상 자식보다 작거나 같음
- 형제 사이에는 대소 관계 없음

2.3 비교 표

구분	최대 힙 (Max Heap)	최소 힙 (Min Heap)
조건	부모 ≥ 자식	부모 ≤ 자식
루트	최대값	최소값
용도	내림차순 정렬, 최대값 반복 추출	오름차순 정렬, 최소값 반복 추출
Python	음수 변환 필요	heapq 기본

---

3. 힙의 구조

3.1 배열로 힙 표현

완전 이진 트리는 배열로 효율적으로 표현 가능

최소 힙 예시:
            10
          /    \
        20      30
       /  \    /
      40  50  60

배열: [10, 20, 30, 40, 50, 60]
인덱스: 0   1   2   3   4   5

인덱스 관계 (0-based):
- 부모: (i - 1) // 2
- 왼쪽 자식: 2 * i + 1
- 오른쪽 자식: 2 * i + 2

3.2 힙 연산 과정

삽입 (Insert) - Heapify Up

삽입 과정 (최소 힙에 5 삽입):

1. 마지막 위치에 삽입
            10                    10
          /    \                /    \
        20      30    →       20      30
       /  \    /  \          /  \    /  \
      40  50  60  [5]       40  50  60   5

2. 부모와 비교하며 위로 이동 (Heapify Up)
            10                    10                     5
          /    \                /    \                 /    \
        20      30    →       20       5     →       20      10
       /  \    /  \          /  \    /  \           /  \    /  \
      40  50  60   5        40  50  60  30         40  50  60  30

결과: 5가 루트로 이동

삭제 (Delete) - Heapify Down

삭제 과정 (최소 힙에서 루트 삭제):

1. 루트(최소값) 반환, 마지막 노드를 루트로 이동
             5                    30
          /    \                /    \
        20      10    →       20      10
       /  \    /              /  \
      40  50  30             40  50

2. 자식과 비교하며 아래로 이동 (Heapify Down)
            30                    10
          /    \                /    \
        20      10    →       20      30
       /  \                  /  \
      40  50                40  50

결과: 10이 루트로 이동

---

4. Python heapq 모듈

4.1 heapq 소개

Python의 heapq 모듈은 **최소 힙(Min Heap)**을 구현합니다.

import heapq

# 기본 사용법
heap = []                    # 빈 힙 생성
heapq.heappush(heap, 3)     # 삽입
heapq.heappush(heap, 1)
heapq.heappush(heap, 2)
print(heap)                  # [1, 3, 2]

min_val = heapq.heappop(heap)  # 최소값 추출
print(min_val)               # 1
print(heap)                  # [2, 3]

4.2 heapq 주요 함수

함수	설명	시간복잡도
heappush(heap, item)	원소 삽입	O(log N)
heappop(heap)	최소값 제거 및 반환	O(log N)
heapify(list)	리스트를 힙으로 변환	O(N)
heappushpop(heap, item)	push 후 pop (효율적)	O(log N)
heapreplace(heap, item)	pop 후 push (효율적)	O(log N)
nsmallest(n, iterable)	가장 작은 n개 반환	O(N log n)
nlargest(n, iterable)	가장 큰 n개 반환	O(N log n)

4.3 함수별 상세 설명 및 예제

4.3.1 heappush(heap, item)

import heapq

heap = []
heapq.heappush(heap, 5)
heapq.heappush(heap, 3)
heapq.heappush(heap, 8)
heapq.heappush(heap, 1)

print(heap)  # [1, 3, 8, 5]
# 참고: 내부 배열 순서와 정렬 순서는 다름
# 하지만 heappop() 하면 항상 최소값이 나옴

4.3.2 heappop(heap)

import heapq

heap = [1, 3, 8, 5]
heapq.heapify(heap)  # 힙 구조 보장

min_val = heapq.heappop(heap)
print(min_val)  # 1
print(heap)     # [3, 5, 8]

# 연속 pop으로 정렬된 순서 얻기
heap = [5, 3, 8, 1, 2]
heapq.heapify(heap)
sorted_list = [heapq.heappop(heap) for _ in range(len(heap))]
print(sorted_list)  # [1, 2, 3, 5, 8]

4.3.3 heapify(list)

import heapq

# 기존 리스트를 힙으로 변환
numbers = [5, 3, 8, 1, 2, 7]
heapq.heapify(numbers)  # O(N)
print(numbers)  # [1, 2, 7, 5, 3, 8]

# 주의: heapify는 in-place로 변환
# 새 리스트를 반환하지 않음

4.3.4 heappushpop(heap, item)

import heapq

# push 후 pop (push + pop보다 효율적)
heap = [1, 3, 5, 7]
result = heapq.heappushpop(heap, 2)
print(result)  # 1 (최소값 반환)
print(heap)    # [2, 3, 5, 7]

# 사용 예: 상위 k개만 유지
def top_k_smallest(nums, k):
    return heapq.nsmallest(k, nums)

4.3.5 heapreplace(heap, item)

import heapq

# pop 후 push (pop + push보다 효율적)
heap = [1, 3, 5, 7]
result = heapq.heapreplace(heap, 10)
print(result)  # 1 (먼저 pop된 값)
print(heap)    # [3, 7, 5, 10]

# 주의: heapreplace는 빈 힙에서 에러 발생

4.3.6 nsmallest / nlargest

import heapq

numbers = [5, 3, 8, 1, 2, 7, 9, 4]

# 가장 작은 3개
smallest_3 = heapq.nsmallest(3, numbers)
print(smallest_3)  # [1, 2, 3]

# 가장 큰 3개
largest_3 = heapq.nlargest(3, numbers)
print(largest_3)  # [9, 8, 7]

# 키 함수 사용
students = [
    {'name': 'Kim', 'score': 85},
    {'name': 'Lee', 'score': 92},
    {'name': 'Park', 'score': 78}
]

# 점수 기준 상위 2명
top_2 = heapq.nlargest(2, students, key=lambda x: x['score'])
print(top_2)
# [{'name': 'Lee', 'score': 92}, {'name': 'Kim', 'score': 85}]

4.4 힙 peek (최소값 확인만)

import heapq

heap = [1, 3, 5, 7]

# peek: 제거 없이 최소값 확인
min_val = heap[0]  # O(1)
print(min_val)  # 1
print(heap)     # [1, 3, 5, 7] (변경 없음)

# 주의: heap[1]이 두 번째로 작은 값은 아님!
# 두 번째 최소값을 알려면 pop 후 다시 peek

---

5. 최대 힙 구현

5.1 음수 변환 방식

Python의 heapq는 최소 힙만 지원하므로, 최대 힙은 음수(-) 변환으로 구현합니다.

import heapq

# 최대 힙 구현: 음수로 저장하고 음수로 꺼내기
max_heap = []

# 삽입: 음수로 저장
heapq.heappush(max_heap, -5)
heapq.heappush(max_heap, -3)
heapq.heappush(max_heap, -8)
heapq.heappush(max_heap, -1)

print(max_heap)  # [-8, -3, -5, -1]

# 추출: 음수를 다시 양수로
max_val = -heapq.heappop(max_heap)
print(max_val)  # 8 (최대값)

# 최대값 확인 (peek)
max_peek = -max_heap[0]
print(max_peek)  # 5

5.2 최대 힙 래퍼 함수

import heapq

class MaxHeap:
    """최대 힙 래퍼 클래스"""

    def __init__(self):
        self.heap = []

    def push(self, val):
        """값 삽입 (음수로 변환)"""
        heapq.heappush(self.heap, -val)

    def pop(self):
        """최대값 추출 (양수로 변환)"""
        return -heapq.heappop(self.heap)

    def peek(self):
        """최대값 확인"""
        return -self.heap[0]

    def __len__(self):
        return len(self.heap)

    def __bool__(self):
        return bool(self.heap)

# 사용 예시
max_heap = MaxHeap()
max_heap.push(5)
max_heap.push(3)
max_heap.push(8)
max_heap.push(1)

print(max_heap.peek())  # 8
print(max_heap.pop())   # 8
print(max_heap.pop())   # 5

5.3 튜플을 이용한 방법

import heapq

# (우선순위, 값) 튜플 사용
# 우선순위가 같으면 값으로 비교

# 최소 힙 (기본)
min_heap = []
heapq.heappush(min_heap, (1, 'low'))
heapq.heappush(min_heap, (3, 'high'))
heapq.heappush(min_heap, (2, 'medium'))

print(heapq.heappop(min_heap))  # (1, 'low')

# 최대 힙 (우선순위에 음수)
max_heap = []
heapq.heappush(max_heap, (-1, 'low'))
heapq.heappush(max_heap, (-3, 'high'))
heapq.heappush(max_heap, (-2, 'medium'))

priority, value = heapq.heappop(max_heap)
print(-priority, value)  # 3 high

---

6. 우선순위 큐

6.1 우선순위 큐란?

우선순위 큐(Priority Queue)는 우선순위에 따라 요소가 처리되는 큐입니다.

• 일반 큐: FIFO (선입선출)
• 우선순위 큐: 우선순위 높은 것이 먼저 출력

6.2 힙으로 우선순위 큐 구현

import heapq

class PriorityQueue:
    """힙 기반 우선순위 큐"""

    def __init__(self):
        self.heap = []
        self.count = 0  # 동일 우선순위 처리용

    def push(self, item, priority):
        """
        아이템 삽입
        priority가 작을수록 높은 우선순위 (최소 힙)
        """
        # (우선순위, 삽입순서, 아이템) - 동일 우선순위면 삽입 순서로
        heapq.heappush(self.heap, (priority, self.count, item))
        self.count += 1

    def pop(self):
        """가장 높은 우선순위 아이템 추출"""
        if self.heap:
            return heapq.heappop(self.heap)[2]  # item만 반환
        return None

    def peek(self):
        """가장 높은 우선순위 아이템 확인"""
        if self.heap:
            return self.heap[0][2]
        return None

    def is_empty(self):
        return len(self.heap) == 0

# 사용 예시
pq = PriorityQueue()
pq.push('치료', 1)      # 높은 우선순위
pq.push('예방접종', 3)   # 낮은 우선순위
pq.push('검진', 2)       # 중간 우선순위

print(pq.pop())  # 치료
print(pq.pop())  # 검진
print(pq.pop())  # 예방접종

6.3 Python queue.PriorityQueue

from queue import PriorityQueue

# PriorityQueue 사용 (스레드 안전)
pq = PriorityQueue()

pq.put((1, '긴급'))
pq.put((3, '보통'))
pq.put((2, '중요'))

print(pq.get())  # (1, '긴급')
print(pq.get())  # (2, '중요')
print(pq.get())  # (3, '보통')

# 주의: heapq가 더 빠름 (스레드 안전 오버헤드 없음)
# 단일 스레드 코딩테스트에서는 heapq 권장

---

7. 구현 코드

7.1 직접 힙 구현 (교육용)

class MinHeap:
    """최소 힙 직접 구현 (교육용)"""

    def __init__(self):
        self.heap = []

    def parent(self, i):
        return (i - 1) // 2

    def left_child(self, i):
        return 2 * i + 1

    def right_child(self, i):
        return 2 * i + 2

    def swap(self, i, j):
        self.heap[i], self.heap[j] = self.heap[j], self.heap[i]

    def push(self, val):
        """삽입 후 heapify up"""
        self.heap.append(val)
        self._heapify_up(len(self.heap) - 1)

    def _heapify_up(self, i):
        """위로 이동하며 힙 속성 유지"""
        while i > 0 and self.heap[self.parent(i)] > self.heap[i]:
            self.swap(i, self.parent(i))
            i = self.parent(i)

    def pop(self):
        """최소값 추출 후 heapify down"""
        if not self.heap:
            return None

        min_val = self.heap[0]
        last = self.heap.pop()

        if self.heap:
            self.heap[0] = last
            self._heapify_down(0)

        return min_val

    def _heapify_down(self, i):
        """아래로 이동하며 힙 속성 유지"""
        smallest = i
        left = self.left_child(i)
        right = self.right_child(i)

        if left < len(self.heap) and self.heap[left] < self.heap[smallest]:
            smallest = left

        if right < len(self.heap) and self.heap[right] < self.heap[smallest]:
            smallest = right

        if smallest != i:
            self.swap(i, smallest)
            self._heapify_down(smallest)

    def peek(self):
        return self.heap[0] if self.heap else None

    def __len__(self):
        return len(self.heap)

# 사용 예시
heap = MinHeap()
heap.push(5)
heap.push(3)
heap.push(8)
heap.push(1)

print(heap.pop())  # 1
print(heap.pop())  # 3
print(heap.pop())  # 5
print(heap.pop())  # 8

7.2 코딩테스트용 간단 구현

import heapq

# 최소 힙 (기본)
min_heap = []
heapq.heappush(min_heap, 3)
heapq.heappush(min_heap, 1)
heapq.heappush(min_heap, 2)

while min_heap:
    print(heapq.heappop(min_heap))  # 1, 2, 3

# 최대 힙 (음수 변환)
max_heap = []
for val in [3, 1, 2]:
    heapq.heappush(max_heap, -val)

while max_heap:
    print(-heapq.heappop(max_heap))  # 3, 2, 1

# 리스트를 힙으로 변환
nums = [5, 3, 8, 1, 2]
heapq.heapify(nums)  # O(n)
print(nums)  # [1, 2, 8, 5, 3]

---

8. 실전 문제

8.1 문제 1: K번째 큰 요소 (LeetCode 215)

문제 설명

정수 배열 nums와 정수 k가 주어질 때,
배열에서 k번째로 큰 요소를 반환하시오.

예시:
nums = [3,2,1,5,6,4], k = 2
return = 5 (정렬하면 [6,5,4,3,2,1]에서 2번째)

정답 코드

import heapq

def findKthLargest(nums, k):
    """
    방법 1: 최대 힙 사용
    - 모든 요소를 최대 힙에 넣고 k번 pop
    """
    max_heap = [-x for x in nums]
    heapq.heapify(max_heap)

    for _ in range(k - 1):
        heapq.heappop(max_heap)

    return -heapq.heappop(max_heap)

def findKthLargest_v2(nums, k):
    """
    방법 2: 최소 힙으로 k개만 유지
    - 크기 k의 최소 힙 유지
    - 힙의 루트가 k번째 큰 값
    """
    min_heap = nums[:k]
    heapq.heapify(min_heap)

    for num in nums[k:]:
        if num > min_heap[0]:
            heapq.heapreplace(min_heap, num)

    return min_heap[0]

# 테스트
print(findKthLargest([3,2,1,5,6,4], 2))  # 5
print(findKthLargest([3,2,3,1,2,4,5,5,6], 4))  # 4

8.2 문제 2: 더 맵게 (프로그래머스)

문제 설명

모든 음식의 스코빌 지수를 K 이상으로 만들어야 합니다.
스코빌 지수가 가장 낮은 두 음식을 섞어 새로운 음식을 만듭니다.
새 음식의 스코빌 = 가장 낮은 음식 + (두 번째로 낮은 음식 * 2)
모든 음식의 스코빌 지수가 K 이상이 될 때까지 반복합니다.
몇 번 섞어야 하는지 return하시오.

예시:
scoville = [1, 2, 3, 9, 10, 12], K = 7
return = 2

정답 코드

import heapq

def solution(scoville, K):
    """
    더 맵게 - 최소 힙 활용

    전략:
    1. 스코빌 지수를 최소 힙으로 관리
    2. 최소값이 K 미만이면 두 개 꺼내서 섞기
    3. 더 이상 섞을 수 없으면 -1 반환
    """
    heapq.heapify(scoville)  # O(n)
    count = 0

    while scoville[0] < K:
        if len(scoville) < 2:
            return -1  # 더 이상 섞을 수 없음

        # 가장 안 매운 것 두 개 꺼내기
        first = heapq.heappop(scoville)
        second = heapq.heappop(scoville)

        # 섞기
        new_scoville = first + second * 2
        heapq.heappush(scoville, new_scoville)

        count += 1

    return count

# 테스트
print(solution([1, 2, 3, 9, 10, 12], 7))  # 2

8.3 문제 3: 디스크 컨트롤러 (프로그래머스)

문제 설명

하드디스크가 요청을 처리할 때, 요청이 들어온 순서대로 처리하지 않고
현재 시점에서 가장 짧은 작업부터 처리하면 평균 대기 시간을 줄일 수 있습니다.

jobs[i] = [요청 시점, 소요 시간]
모든 요청의 평균 반환 시간을 최소화하시오.

예시:
jobs = [[0, 3], [1, 9], [2, 6]]
return = 9

정답 코드

import heapq

def solution(jobs):
    """
    디스크 컨트롤러 - SJF (Shortest Job First)

    전략:
    1. 현재 시점에서 처리 가능한 작업 중 가장 짧은 것 선택
    2. 최소 힙으로 소요 시간 기준 관리
    """
    jobs.sort(key=lambda x: x[0])  # 요청 시점 순 정렬
    n = len(jobs)

    heap = []  # (소요 시간, 요청 시점)
    total_time = 0
    current_time = 0
    job_index = 0

    while job_index < n or heap:
        # 현재 시점까지 도착한 작업을 힙에 추가
        while job_index < n and jobs[job_index][0] <= current_time:
            heapq.heappush(heap, (jobs[job_index][1], jobs[job_index][0]))
            job_index += 1

        if heap:
            # 가장 짧은 작업 처리
            duration, arrival = heapq.heappop(heap)
            current_time += duration
            total_time += current_time - arrival  # 반환 시간
        else:
            # 처리할 작업이 없으면 다음 작업 시점으로 이동
            current_time = jobs[job_index][0]

    return total_time // n

# 테스트
print(solution([[0, 3], [1, 9], [2, 6]]))  # 9

8.4 문제 4: 이중 우선순위 큐 (프로그래머스)

문제 설명

이중 우선순위 큐는 다음 연산을 지원합니다:
- I 숫자: 큐에 주어진 숫자 삽입
- D 1: 최대값 삭제
- D -1: 최소값 삭제

모든 연산을 처리한 후 큐가 비어있으면 [0, 0]
비어있지 않으면 [최대값, 최소값] 반환

예시:
operations = ["I 16", "I -5643", "D -1", "D 1", "D 1", "I 123", "D -1"]
return = [0, 0]

정답 코드

import heapq

def solution(operations):
    """
    이중 우선순위 큐

    전략:
    최소 힙과 최대 힙 동시 관리 + 삭제 여부 추적
    """
    min_heap = []
    max_heap = []
    entry_count = {}  # 유효한 요소 추적

    for op in operations:
        cmd, val = op.split()
        val = int(val)

        if cmd == 'I':
            heapq.heappush(min_heap, val)
            heapq.heappush(max_heap, -val)
            entry_count[val] = entry_count.get(val, 0) + 1

        elif cmd == 'D':
            # 유효하지 않은 요소 제거
            while min_heap and entry_count.get(min_heap[0], 0) == 0:
                heapq.heappop(min_heap)
            while max_heap and entry_count.get(-max_heap[0], 0) == 0:
                heapq.heappop(max_heap)

            if val == 1 and max_heap:  # 최대값 삭제
                max_val = -heapq.heappop(max_heap)
                entry_count[max_val] -= 1
            elif val == -1 and min_heap:  # 최소값 삭제
                min_val = heapq.heappop(min_heap)
                entry_count[min_val] -= 1

    # 유효하지 않은 요소 정리
    while min_heap and entry_count.get(min_heap[0], 0) == 0:
        heapq.heappop(min_heap)
    while max_heap and entry_count.get(-max_heap[0], 0) == 0:
        heapq.heappop(max_heap)

    if not min_heap:
        return [0, 0]

    return [-max_heap[0], min_heap[0]]

# 테스트
print(solution(["I 16", "D 1"]))  # [0, 0]
print(solution(["I 7", "I 5", "I -5", "D -1"]))  # [7, 5]

8.5 문제 5: 다익스트라 알고리즘 (힙 활용)

import heapq

def dijkstra(graph, start):
    """
    다익스트라 알고리즘 - 힙 활용

    graph: {노드: [(거리, 연결노드), ...]}
    """
    distances = {node: float('inf') for node in graph}
    distances[start] = 0

    heap = [(0, start)]  # (거리, 노드)

    while heap:
        current_dist, current_node = heapq.heappop(heap)

        # 이미 처리된 노드면 스킵
        if current_dist > distances[current_node]:
            continue

        for dist, neighbor in graph[current_node]:
            new_dist = current_dist + dist

            if new_dist < distances[neighbor]:
                distances[neighbor] = new_dist
                heapq.heappush(heap, (new_dist, neighbor))

    return distances

# 예시
graph = {
    'A': [(1, 'B'), (4, 'C')],
    'B': [(2, 'C'), (5, 'D')],
    'C': [(1, 'D')],
    'D': []
}
print(dijkstra(graph, 'A'))
# {'A': 0, 'B': 1, 'C': 3, 'D': 4}

---

9. 힙 문제 유형 정리

9.1 힙으로 풀어야 하는 유형

키워드	확률	설명
"최대/최소 빈번"	높음	최대값 또는 최소값을 반복적으로 구함
"K번째"	높음	K번째 큰/작은 값
"우선순위"	높음	우선순위에 따른 처리
"다익스트라"	100%	최단 경로 알고리즘
"상위 K개"	높음	가장 큰/작은 K개 요소
"정렬 + 중간"	중간	중간값 찾기 (두 개의 힙 사용)

9.2 힙 문제 판별법

문제에서 다음 패턴이 보이면 힙을 고려하세요:

1. 최대/최소값을 여러 번 구해야 하는 문제
   → 매번 정렬하면 비효율적, 힙 사용

2. K번째 요소를 찾는 문제
   → 힙으로 K개만 유지

3. 우선순위 기반 처리
   → 우선순위 큐로 구현

4. 동적으로 정렬 상태를 유지해야 하는 문제
   → 삽입/삭제 후에도 최대/최소 빠르게 접근

5. 다익스트라, 프림 알고리즘
   → 힙 기반 구현이 효율적

9.3 대표적인 힙 문제들

문제 유형	예시
K번째 요소	K번째 큰 수, 상위 K개
합치기	더 맵게, 돌 합치기
스케줄링	디스크 컨트롤러, 작업 스케줄링
최단 경로	다익스트라, 프림
중간값	스트리밍 중간값
이중 힙	이중 우선순위 큐

---

10. 시간복잡도

10.1 힙 연산 시간복잡도

연산	시간복잡도	설명
heappush	O(log N)	삽입 후 heapify up
heappop	O(log N)	제거 후 heapify down
heapify	O(N)	리스트를 힙으로 변환
peek (heap[0])	O(1)	최소값 확인
nsmallest(k)	O(N log k)	가장 작은 k개
nlargest(k)	O(N log k)	가장 큰 k개

10.2 힙 정렬 시간복잡도

# 힙 정렬
def heap_sort(arr):
    heapq.heapify(arr)  # O(N)
    return [heapq.heappop(arr) for _ in range(len(arr))]  # O(N log N)

# 전체 시간복잡도: O(N log N)
# 공간복잡도: O(1) (in-place) 또는 O(N)

10.3 정렬 vs 힙 비교

상황	정렬	힙
전체 정렬 필요	O(N log N) ✓	O(N log N)
상위 K개만 필요	O(N log N)	O(N log K) ✓
동적 삽입/삭제	O(N)	O(log N) ✓
최대/최소 1번만	O(N) ✓	O(N)

---

참고 자료

heapq 활용 팁

import heapq

# 1. 기존 리스트를 힙으로 (in-place)
nums = [5, 3, 8, 1]
heapq.heapify(nums)  # nums가 직접 변경됨

# 2. 상위 K개 (정렬보다 효율적)
top_3 = heapq.nlargest(3, nums)  # O(N log 3)

# 3. 튜플 활용 (다중 기준 정렬)
# (우선순위1, 우선순위2, 값)
heap = []
heapq.heappush(heap, (1, 'a', 'data1'))
heapq.heappush(heap, (1, 'b', 'data2'))

# 4. 음수 변환으로 최대 힙
heapq.heappush(heap, -value)
max_val = -heapq.heappop(heap)

주의사항

import heapq

# 빈 힙에서 pop 시 에러
heap = []
heapq.heappop(heap)  # IndexError

# 항상 확인 후 pop
if heap:
    heapq.heappop(heap)

# heapify는 in-place (반환값 None)
nums = [5, 3, 8]
result = heapq.heapify(nums)  # result는 None!
# nums가 직접 변경됨

힙 vs 다른 자료구조 선택

자료구조	최소/최대 접근	삽입	삭제	탐색
정렬 배열	O(1)	O(N)	O(N)	O(log N)
힙	O(1)	O(log N)	O(log N)	O(N)
BST (균형)	O(log N)	O(log N)	O(log N)	O(log N)

힙 선택 기준:

• 최대/최소만 자주 필요 → 힙 ✓
• 특정 값 탐색이 자주 필요 → BST
• 전체 정렬 필요 → 정렬 알고리즘