[Python] 우선순위 큐와 힙 (Priority Queue & Heap)

 

우선순위 큐 (Priority Queue)

 

우선순위 큐는 큐(Queue) 자료구조의 변형으로, 각 요소가 우선순위(priority)를 가지고 있습니다.

큐에서 데이터를 꺼낼 때 우선순위가 가장 높은 요소가 먼저 나옵니다.

일반적인 큐는 FIFO(선입선출) 방식으로 작동하지만, 우선순위 큐는 우선순위에 따라 데이터를 처리합니다.

 

힙 (Heap)

 

힙은 이진 트리(Binary Tree) 기반의 완전 이진 트리(Complete Binary Tree)입니다.

 

이진 트리란?

- 각 노드가 최대 두 개의 자식 노드를 가지는 트리 구조입니다.

 

완전 이진트리란?

- 말단 노드를 제외하고 모든 노드가 2개의 자식을 갖고 있는 이진 트리입니다.

 

 

 

각 노드가 특정한 규칙을 따르는 트리 자료구조입니다.

 

힙은 각 노드가 하위 노드보다 크거나 작은 우선순위를 가집니다.

최대 힙에서는 부모 노드가 자식 노드보다 항상 크고, 최소 힙에서는 부모 노드가 자식 노드보다 항상 작습니다.

 

힙은 우선순위 큐를 구현하는 데 자주 사용됩니다.

최대 힙(Max Heap)과 최소 힙(Min Heap) 두 가지 유형이 있습니다.

 

최대 힙 : 부모 노드가 자식 노드보다 크거나 같습니다.
최소 힙 : 부모 노드가 자식 노드보다 작거나 같습니다.

 

 

최소 힙 Python 예시 코드

 

import heapq

# 힙 생성 (리스트를 힙으로 변환)
heapq.heapify(list) # 시간 복잡도 : O(n)

# 원소 추가
heapq.heappush(heap, item) # 시간 복잡도 : O(log n)

# 원소 삭제 및 변환
heapq.heappop(heap) # 시간 복잡도 : O(log n)

 

최대 힙 Python 예시 코드

 

import heapq

heap = [-n for n in nums] # 

# 힙 생성 (리스트를 힙으로 변환)
heapq.heapify(list) # 시간 복잡도 : O(n)

# 원소 추가
heapq.heappush(heap, -item) # 시간 복잡도 : O(log n)

# 원소 삭제 및 변환
-heapq.heappop(heap) # 시간 복잡도 : O(log n)