[TIL] 250629 우선순위 큐(힙(Heap))

1. 개념 정리: 힙(Heap) = 우선순위 큐

• 우선순위 큐는 일반적인 큐와 달리, 값의 크기에 따라 먼저 나가는 순서가 결정됨
• 파이썬의 heapq는 최소 힙(min heap) 기반:
  • 항상 가장 작은 값이 먼저 나옴
• 최대 힙(max heap)을 쓰고 싶을 땐 값을 음수로 저장해서 우회

 

2. 힙 사용법 (파이썬 heapq)

- 최소 힙 (기본 동작)

import heapq

heap = []

# 삽입: heappush
heapq.heappush(heap, 4)
heapq.heappush(heap, 1)
heapq.heappush(heap, 7)

# 출력 (가장 작은 값)
print(heapq.heappop(heap))  # 1
print(heapq.heappop(heap))  # 4
print(heapq.heappop(heap))  # 7

 

- 최대 힙 (음수 활용)

import heapq

heap = []

# 값을 음수로 넣어 최대 힙처럼 사용
heapq.heappush(heap, -4)
heapq.heappush(heap, -1)
heapq.heappush(heap, -7)

# pop할 때 다시 음수로 바꿔줌
print(-heapq.heappop(heap))  # 7
print(-heapq.heappop(heap))  # 4
print(-heapq.heappop(heap))  # 1

3. 힙 주요 함수 정리

함수명	설명	시간 복잡도
heapq.heappush(heap, item)	item을 힙에 추가	O(log n)
heapq.heappop(heap)	가장 작은 item을 제거하고 반환	O(log n)
heapq.heapify(list)	기존 리스트를 in-place로 힙으로 만듦	O(log n)
heapq.heappushpop(heap, item)	item을 넣고, 가장 작은 값 바로 꺼냄 (더 빠름)	O(n)
heapq.nlargest(n, iterable)	가장 큰 n개 요소 리턴 (정렬 아님)	O(n log k)
heapq.nsmallest(n, iterable)	가장 작은 n개 요소 리턴	O(n log k)

4. 우선순위가 튜플일 경우

(우선순위, 값) 형식으로 넣으면 우선순위 기준 정렬됨

import heapq

tasks = []
heapq.heappush(tasks, (2, "cleaning"))
heapq.heappush(tasks, (1, "study"))
heapq.heappush(tasks, (3, "sleep"))

print(heapq.heappop(tasks))  # (1, 'study') -> 가장 우선순위 높은 작업

 

5. heapq.nsmallest(n, iterable)

heapq.nsmallest(n, iterable)는 iterable(반복 가능한 자료)에서 가장 작은 값 n개를 찾아서 정렬된 리스트로 반환해주는 함수

 

사용법

import heapq

nums = [10, 4, 1, 20, 7]

# 가장 작은 3개 원소 반환
smallest = heapq.nsmallest(3, nums)

print(smallest)  # [1, 4, 7]

 

• 정렬된 결과를 반환함 (min → max)
• 내부적으로는 최대 힙(Max Heap) 크기 n 유지 → 시간 복잡도: O(n log k)

nsmallest + key 인자 (정렬 기준 커스텀)

students = [
    {"name": "Alice", "score": 82},
    {"name": "Bob", "score": 91},
    {"name": "Charlie", "score": 78}
]

# 점수(score)가 가장 낮은 2명
top2 = heapq.nsmallest(2, students, key=lambda x: x["score"])

for s in top2:
    print(s["name"], s["score"])
# 출력:
# Charlie 78
# Alice 82

 

6. 튜플로 여러 우선순위를 동시에 설정하기

• 파이썬은 튜플을 비교할 때 자동으로 사전식(lexicographical) 비교를 수행함.
  즉 (a, b, c)끼리 비교할 때는
  1. 첫 요소 a를 먼저 비교하고
  2. 같으면 두 번째 요소 b를 비교하며
  3. 그래도 같으면 세 번째 요소 c를 기준으로 비교합니다.
  이 성질 덕분에 heapq에 아래처럼 튜플을 넣으면:

import heapq

heap = []
heapq.heappush(heap, (priority1, priority2, data))

• priority1이 작을수록 더 우선
• 같다면 priority2 비교
• 또 같으면 data(또는 다른 요소)까지 비교

이렇게 다중 우선순위 기준을 쉽게 적용할 수 있음

실전 예제: 세 가지 기준으로 정렬되는 힙

학생들을 (등급, 나이, 이름) 기준으로 우선순위를 주려고 한다면:

import heapq

students = [
    ('A', 22, 'Charlie'),
    ('B', 20, 'Alice'),
    ('A', 20, 'Bob'),
    ('A', 22, 'Anne'),
]

heap = []
for grade, age, name in students:
    heapq.heappush(heap, (grade, age, name))

while heap:
    print(heapq.heappop(heap))

 

결과는 아래와 같음

('A', 20, 'Bob')
('A', 22, 'Anne')
('A', 22, 'Charlie')
('B', 20, 'Alice')

• 등급 A 우선,
• 나이 같다면 20살 먼저,
• 나이도 같다면 이름 알파벳 순

이렇게 튜플을 그대로 넣는 것만으로 다중 우선순위를 적용할 수 있음