[leetcode] 힙(heap)이란?

힙(Heap)은 우선순위 큐를 구현하는 자료구조야.

핵심 개념 힙은 “가장 작은 값(또는 가장 큰 값)을 빠르게 꺼낼 수 있는” 자료구조야.

       1          ← 항상 최솟값이 맨 위 (min-heap)
      / \
     3   2
    / \
   7   4

주요 연산과 시간복잡도

연산	시간복잡도	설명
heappush	O(log n)	값 추가
heappop	O(log n)	최솟값 꺼내기
heap[0]	O(1)	최솟값 확인 (꺼내지 않음)

리스트와 비교

# 리스트로 최솟값 찾기
min_val = min(arr)        # O(n) - 매번 전체 탐색

# 힙으로 최솟값 찾기  
min_val = heapq.heappop(heap)  # O(log n) - 훨씬 빠름

Python 사용법

import heapq

# 빈 리스트를 힙처럼 사용
heap = []

# 값 추가
heapq.heappush(heap, 5)
heapq.heappush(heap, 2)
heapq.heappush(heap, 8)
heapq.heappush(heap, 1)

print(heap)  # [1, 2, 8, 5] - 내부 구조 (정렬된 건 아님)

# 최솟값 꺼내기 (제거됨)
print(heapq.heappop(heap))  # 1
print(heapq.heappop(heap))  # 2
print(heapq.heappop(heap))  # 5
print(heapq.heappop(heap))  # 8

이 문제에서 힙을 쓰는 이유 “k개 중 가장 작은 것을 버리고 싶다” → min-heap 사용

heap = []
for n1 in nums1_values:
    heapq.heappush(heap, n1)
    
    if len(heap) > k:
        heapq.heappop(heap)  # 가장 작은 값 제거 → 큰 k개만 유지

• “k번째로 큰/작은 값” 찾기
• “상위 k개” 유지하기
• 실시간으로 최솟값/최댓값 추적
• 다익스트라 같은 그래프 알고리즘

#heap, #min-heap, #우선순위큐, #자료구조