Ch.4 스택과 큐

우선순위 큐(Heap)

힙(Heap)의 구조와 우선순위 큐 원리를 이해한다heapq 모듈을 활용해 Kth Largest Element 문제를 해결한다

응급실에서는 먼저 온 사람이 먼저가 아닙니다

응급실은 위급한 환자가 먼저 치료받습니다. 이처럼 '우선순위'에 따라 순서가 정해지는 것이 우선순위 큐이며, 그 내부 구현이 바로 힙(Heap)입니다.

정렬하면 O(n log n)인데, 매번 정렬하지 않고 최솟값을 O(log n)에 꺼낼 수 있을까?

이진 힙(Binary Heap)은 '부모 ≤ 자식' 규칙으로 최솟값을 항상 루트에 유지합니다.

lightbulb

핵심 개념

힙(Heap)

부모 노드가 자식보다 항상 작은(또는 큰) 완전 이진 트리

우선순위 큐

우선순위가 높은 원소를 먼저 꺼내는 자료구조

article

핵심 내용

힙(Heap) = 완전 이진 트리 + 부모 ≤ 자식 (Min Heap)

Min Heap 규칙 루트 = 전체에서 가장 작은 값 부모 ≤ 왼쪽 자식 부모 ≤ 오른쪽 자식 완전 이진 트리 (왼쪽부터 채움)

Python의 heapq 모듈은 Min Heap을 제공합니다

import heapq

# 빈 리스트에 원소 추가 (heappush)
heap = []
heapq.heappush(heap, 30)
heapq.heappush(heap, 10)
heapq.heappush(heap, 20)
print(heap)         # [10, 30, 20]

# 최솟값 꺼내기 (heappop)
smallest = heapq.heappop(heap)
print(smallest)     # 10
print(heap)         # [20, 30]

# 최솟값 확인만 (제거X)
print(heap[0])      # 20

heapq는 Min Heap만 지원 Max Heap은 부호를 뒤집어 구현합니다

import heapq

# Max Heap: 음수로 넣고, 꺼낼 때 부호 복원
max_heap = []
heapq.heappush(max_heap, -30)
heapq.heappush(max_heap, -10)
heapq.heappush(max_heap, -20)

largest = -heapq.heappop(max_heap)
print(largest)  # 30

이 트릭은 면접에서 정말 자주 쓰입니다 반드시 외워두세요!

배열에서 K번째로 큰 원소를 찾아라 LeetCode #215 — 면접 단골 문제!

import heapq

def findKthLargest(nums, k):
    # 크기 k의 Min Heap 유지
    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

왜 Min Heap으로 Kth Largest를 찾나? k개짜리 Min Heap을 유지하면 → heap[0] = k개 중 최솟값 = 전체에서 k번째로 큰 값 시간: O(n log k) 공간: O(k)

heapq.heappop()의 시간복잡도는?

Python heapq로 Max Heap을 만들려면 원소에 ___를 곱해서 넣는다

원소 × ___ → heappush

heapq.heapify()의 시간복잡도는 O(n log n)이다

힙 마스터!

key

핵심 용어

🌲

힙(Heap)

부모 ≤ 자식인 완전 이진 트리

🏥

우선순위 큐

우선순위 높은 원소를 먼저 꺼내는 ADT

⬆️

heappush(heap, x)

O(log n) — 삽입 후 위로 올림

⬇️

heappop(heap)

O(log n) — 루트 제거 후 재정렬

👀

heap[0]

O(1) — 최솟값 확인

🔨

heapify(list)

O(n) — 리스트를 힙으로 변환

edit_note

정리 노트

우선순위 큐(Heap)

heapq 핵심 연산

heappush
O(log n) — 삽입
heappop
O(log n) — 최솟값 제거
heap[0]
O(1) — 최솟값 확인
heapify
O(n) — 리스트를 힙으로 변환

면접 패턴

Max Heap
-1을 곱해서 넣고, 꺼낼 때 부호 복원
Kth Largest
크기 k의 Min Heap 유지 → heap[0]이 답
★

heapify는 O(n)이고, n번 heappush는 O(n log n) — 차이를 설명할 수 있어야 합니다!

image

시각 자료

다이어그램: ds-d33
check_circle

핵심 정리

  • 1힙 = 부모 ≤ 자식인 완전 이진 트리
  • 2heapq: push/pop O(log n), heapify O(n)
  • 3Max Heap은 -1 곱하기 트릭으로 구현

퀴즈와 인터랙션으로 더 깊이 학습하세요

play_circle인터랙티브 레슨 시작