🎯 1. 힙(Heap) 기본 개념 ⭐⭐⭐

힙이란?

# 힙(Heap): 완전 이진 트리
# - 최소 힙: 부모 노드가 자식 노드보다 항상 작음
# - 최대 힙: 부모 노드가 자식 노드보다 항상 큼

# 최소 힙 예시:
#       1
#      / \\
#     3   2
#    / \\
#   5   4
#
# 배열 표현: [1, 3, 2, 5, 4]
# 부모 인덱스: i
# 왼쪽 자식: 2*i + 1
# 오른쪽 자식: 2*i + 2

# 특징:
# - 삽입: O(log n)
# - 최솟값 추출: O(log n)
# - 최솟값 확인: O(1)

Python의 heapq 모듈

import heapq

# Python의 heapq는 최소 힙만 지원!
# 리스트를 힙으로 변환
arr = [3, 1, 4, 1, 5, 9, 2, 6]
heapq.heapify(arr)  # O(n)으로 힙 생성
print(arr)  # [1, 1, 2, 3, 5, 9, 4, 6]

# 주의: 리스트처럼 보이지만 힙 구조!
# arr[0]만 최솟값 보장, 나머지는 힙 속성만 만족

기본 연산

import heapq

heap = []

# 삽입 - O(log n)
heapq.heappush(heap, 3)
heapq.heappush(heap, 1)
heapq.heappush(heap, 4)
heapq.heappush(heap, 1)
heapq.heappush(heap, 5)
print(heap)  # [1, 1, 4, 3, 5]

# 최솟값 추출 - O(log n)
min_val = heapq.heappop(heap)
print(min_val)  # 1
print(heap)  # [1, 3, 4, 5]

# 최솟값 확인 (제거 안 함) - O(1)
print(heap[0])  # 1

# 리스트를 힙으로 변환 - O(n)
arr = [3, 1, 4, 1, 5, 9, 2, 6]
heapq.heapify(arr)
print(arr[0])  # 1 (최솟값)

🎯 2. 최소 힙 활용 패턴 ⭐⭐⭐

패턴 1: K번째 작은 원소

import heapq

def kth_smallest(arr, k):
    """
    K번째 작은 원소 찾기
    """
    # 방법 1: heapify 후 k번 pop
    heap = arr[:]
    heapq.heapify(heap)  # O(n)

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

    return heapq.heappop(heap)

arr = [7, 10, 4, 3, 20, 15]
print(kth_smallest(arr, 3))  # 7 (3번째 작은 수)

# 방법 2: nsmallest 사용 (더 간단!)
def kth_smallest_v2(arr, k):
    return heapq.nsmallest(k, arr)[-1]

print(kth_smallest_v2(arr, 3))  # 7

패턴 2: K개의 작은 원소

import heapq

arr = [7, 10, 4, 3, 20, 15]

# 가장 작은 3개
smallest_3 = heapq.nsmallest(3, arr)
print(smallest_3)  # [3, 4, 7]

# 가장 큰 3개
largest_3 = heapq.nlargest(3, arr)
print(largest_3)  # [20, 15, 10]

# key 함수 사용
students = [('Alice', 85), ('Bob', 90), ('Charlie', 75)]

# 점수 낮은 순 3명
lowest_3 = heapq.nsmallest(3, students, key=lambda x: x[1])
print(lowest_3)  # [('Charlie', 75), ('Alice', 85), ('Bob', 90)]

# 점수 높은 순 2명
top_2 = heapq.nlargest(2, students, key=lambda x: x[1])
print(top_2)  # [('Bob', 90), ('Alice', 85)]

패턴 3: 정렬된 병합 (Merge K Sorted Lists)

import heapq

def merge_sorted_lists(lists):
    """
    여러 정렬된 리스트를 하나로 병합
    LeetCode 23: Merge k Sorted Lists
    """
    heap = []

    # 각 리스트의 첫 원소를 힙에 추가
    # (값, 리스트 인덱스, 원소 인덱스)
    for i, lst in enumerate(lists):
        if lst:
            heapq.heappush(heap, (lst[0], i, 0))

    result = []

    while heap:
        val, list_idx, elem_idx = heapq.heappop(heap)
        result.append(val)

        # 다음 원소가 있으면 힙에 추가
        if elem_idx + 1 < len(lists[list_idx]):
            next_val = lists[list_idx][elem_idx + 1]
            heapq.heappush(heap, (next_val, list_idx, elem_idx + 1))

    return result

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

# 또는 heapq.merge 사용 (더 간단!)
result = list(heapq.merge(*lists))
print(result)  # [1, 1, 2, 3, 4, 4, 5, 6]

🎯 3. 최대 힙 구현 ⭐⭐⭐

음수 변환 트릭

import heapq

# Python은 최소 힙만 지원
# 최대 힙을 만들려면: 음수로 변환!

heap = []

# 최대 힙처럼 사용
numbers = [3, 1, 4, 1, 5, 9, 2, 6]

for num in numbers:
    heapq.heappush(heap, -num)  # 음수로 저장

# 최댓값 추출
max_val = -heapq.heappop(heap)
print(max_val)  # 9

# 현재 최댓값 확인
current_max = -heap[0]
print(current_max)  # 6

최대 힙 클래스 구현