파이썬 heapq : 힙큐 사용법 정리

 

🔍 힙(Heap)이란?

힙은 완전 이진 트리 기반의 자료구조로, 최솟값이나 최댓값을 빠르게 찾을 수 있도록 정렬된 구조이다.

• 최소 힙 (Min Heap): 부모 노드 ≤ 자식 노드
• 최대 힙 (Max Heap): 부모 노드 ≥ 자식 노드

파이썬의 heapq는 최소 힙을 기본으로 제공한다.

📦 heapq란?

파이썬 표준 라이브러리 heapq는 리스트를 힙처럼 다룰 수 있도록 해주는 함수 모음이다.

import heapq

🧩 heapq 함수 정리

함수명	설명
heapq.heappush(heap, item)	힙에 item 삽입
heapq.heappop(heap)	힙에서 가장 작은 원소 꺼냄
heapq.heapify(iterable)	리스트를 힙 구조로 변환
heapq.heappushpop(heap, item)	item 삽입 후 최소값 제거
heapq.heapreplace(heap, item)	최소값 제거 후 item 삽입
heapq.nlargest(n, iterable)	가장 큰 값 n개 반환
heapq.nsmallest(n, iterable)	가장 작은 값 n개 반환

📌 1. 힙 생성 및 기본 사용법

import heapq

heap = []
heapq.heappush(heap, 4)
heapq.heappush(heap, 1)
heapq.heappush(heap, 7)

print(heapq.heappop(heap))  # 1 (가장 작은 값)

📌 2. 여러 원소를 힙에 넣는 법

✅ heapify() 사용

nums = [5, 2, 8, 1, 9]
heapq.heapify(nums)
print(nums)

✅ 여러 개 heappush()

heap = []
for x in [5, 2, 8, 1, 9]:
    heapq.heappush(heap, x)

📌 3. heappushpop()과 heapreplace()

✅ heappushpop(): 푸시 후 팝

heap = [3, 4, 5]
heapq.heapify(heap)
result = heapq.heappushpop(heap, 2)
print(result)  # 2

✅ heapreplace(): 팝 후 푸시

heap = [3, 4, 5]
heapq.heapify(heap)
result = heapq.heapreplace(heap, 10)
print(result)  # 3
print(heap)    # [4, 10, 5]

📌 4. nlargest() / nsmallest()

nums = [5, 1, 8, 3, 7, 2]
print(heapq.nlargest(3, nums))   # [8, 7, 5]
print(heapq.nsmallest(3, nums))  # [1, 2, 3]

📌 5. 최대 힙(Max Heap) 만들기

max_heap = []
for x in [5, 1, 8]:
    heapq.heappush(max_heap, -x)

print(-heapq.heappop(max_heap))  # 8

📌 6. 우선순위 큐로 사용하기

tasks = []
heapq.heappush(tasks, (2, "eat"))
heapq.heappush(tasks, (1, "code"))
heapq.heappush(tasks, (3, "sleep"))

print(heapq.heappop(tasks))  # (1, "code")

우선순위가 같은 경우 입력 순서를 유지하려면:

import itertools

counter = itertools.count()
tasks = []
heapq.heappush(tasks, (1, next(counter), "code"))
heapq.heappush(tasks, (1, next(counter), "eat"))
print(heapq.heappop(tasks))  # (1, 0, "code")

📌 7. n번째 큰 수 찾기

arr = [5, 2, 8, 1, 9]
n = 3
nth_largest = heapq.nlargest(n, arr)[-1]
print(nth_largest)  # 5

또는 메모리를 아끼려면:

def nth_largest(nums, n):
    heap = nums[:n]
    heapq.heapify(heap)
    for x in nums[n:]:
        if x > heap[0]:
            heapq.heappushpop(heap, x)
    return heap[0]

📌 8. 힙 정렬 (Heap Sort)

def heap_sort(iterable):
    h = []
    for value in iterable:
        heapq.heappush(h, value)
    return [heapq.heappop(h) for _ in range(len(h))]

print(heap_sort([5, 2, 8, 1, 9]))  # [1, 2, 5, 8, 9]

✅ 마무리 요약

기능	방법
힙 초기화	heapify(list)
원소 삽입	heappush(heap, item)
최소값 제거	heappop(heap)
최대 힙 구현	-값 또는 (-우선순위, 값)
n번째 큰 값	nlargest(n, arr)[-1]
우선순위 큐	(priority, count, item) 형태 사용

---

heapq는 알고리즘 문제 풀이, 우선순위 큐, 힙 정렬 등 다양한 상황에서 매우 유용하게 사용된다. 기본적인 리스트로도 효율적인 힙 자료구조를 구현할 수 있도록 해주기 때문에 꼭 익혀두는 것이 좋다.