힙(Heap)과 우선순위 큐(Priority Queue)

• 우선순위 큐를 구현하기 위한 파이썬이 도구로 heap과 PriorityQueue()가 있다.

• heap이란 여러 개의 값 중에서 가장 크거나 작은 값을 빠르게(O(1)) 찾기 위해 만든 이진 트리이다.

• 완전 이진 트리이며, 부모의 값은 자식의 값보다 항상 크거나(max heap) 작다(min heap).

• 완전 이진 트리이므로 데이터의 삭제/삽입 모두 O(log(N))이다.

아래는 GPT의 도움을 받아 정리한 내용이다.

heap, PriorityQueue 기본 내용

import heapq
from queue import PriorityQueue

# 1. 힙(heapq)에서 기본 동작
heap = []
heapq.heappush(heap, 5)
heapq.heappush(heap, 3)
heapq.heappush(heap, 5)  # 중복된 값 허용
heapq.heappush(heap, 1)

print("\nHeapq with duplicates:")
while heap:
    print(heapq.heappop(heap))  # 출력: 1, 3, 5, 5

# 2. 힙에서 튜플 비교
heap = []
heapq.heappush(heap, (1, "B"))
heapq.heappush(heap, (1, "A"))  # 첫 번째 값 같으면 두 번째 값 비교
heapq.heappush(heap, (2, "C"))
heapq.heappush(heap, (1, "C"))

print("\nHeapq with tuples:")
while heap:
    print(heapq.heappop(heap))  # 출력: (1, 'A'), (1, 'B'), (1, 'C'), (2, 'C')

# 3. 중복 삽입 방지
heap = []
seen = set()  # 중복 확인용 집합
values = [5, 3, 5, 1]
for val in values:
    if val not in seen:
        heapq.heappush(heap, val)
        seen.add(val)

print("\nHeapq without duplicates:")
while heap:
    print(heapq.heappop(heap))  # 출력: 1, 3, 5

# 4. PriorityQueue 사용
pq = PriorityQueue()
pq.put((2, "B"))
pq.put((1, "A"))
pq.put((3, "C"))

print("\nPriorityQueue:")
while not pq.empty():
    print(pq.get())  # 출력: (1, 'A'), (2, 'B'), (3, 'C')

# 5. 커스텀 클래스 힙 정렬
class Node:
    def __init__(self, val, name):
        self.val = val
        self.name = name

    def __lt__(self, other):
        return self.val < other.val  # 값(val)을 기준으로 비교

heap = []
heapq.heappush(heap, Node(10, "A"))
heapq.heappush(heap, Node(5, "B"))
heapq.heappush(heap, Node(7, "C"))

print("\nHeapq with custom class:")
while heap:
    node = heapq.heappop(heap)
    print(node.val, node.name)  # 출력: 5 B, 7 C, 10 A

heap, PriorityQueue 비교

heap 주요 메서드

heapq.heappush(heap, x)	힙에 요소 x를 추가합니다.
heapq.heappop(heap)		힙에서 가장 작은 요소를 제거하고 반환합니다.
heapq.heapify(heap)		기존 리스트를 힙 구조로 변환합니다.
heapq.nlargest(n, iter)	이터러블에서 가장 큰 요소 n개를 반환합니다.
heapq.nsmallest(n, iter)이터러블에서 가장 작은 요소 n개를 반환합니다.

PriorityQueue 주요 메서드

put(item)	우선순위 큐에 요소를 추가합니다.
get()		우선순위가 가장 높은 요소를 제거하고 반환합니다.
qsize()		큐에 남아 있는 항목의 개수를 반환합니다.
empty()		큐가 비어 있는지 확인합니다.
full()		큐가 가득 찼는지 확인합니다.

비교

특징	heapq	PriorityQueue
기본 구현 구조	최소 힙 (min-heap)	최소 힙 (min-heap)
스레드 안전성	✗ (스레드 안전하지 않음)	✓ (스레드 안전 제공)
사용 편의성	낮음 (리스트를 직접 관리해야 함)	높음 (큐 인터페이스 제공)
성능	빠름 (최소한의 오버헤드)	상대적으로 느림 (스레드 동기화로 인한 오버헤드)
멀티스레드 환경	별도의 동기화 필요	동기화 제공, 멀티스레드에 적합
유연성	높음 (튜플, 커스텀 객체로 비교 가능)	낮음 (기본적으로 값만 다룸)
활용 예	정렬, 커스텀 정렬 작업	생산자-소비자 모델, 멀티스레드 환경에서 큐 관리

• 단순한 힙 연산이 필요한 경우 → heapq가 더 빠르고 유연합니다.
• 멀티스레드 환경에서 안전한 큐가 필요하면 → PriorityQueue를 사용하는 것이 적합합니다.