[Python] 우선순위큐 구현 - 파이썬 heapq 모듈

1. 우선순위 큐(Priority Queue)란?

• 자료구조 중 큐(Queue)는 FIFO(First IN First Out) 즉, 먼저 들어온 데이터가 먼저 나가는 자료구조이다.
• 우선순위 큐는 우선순위가 높은 데이터가 먼저 나가는 자료구조이다. 큐는 삽입된 순서, 우선순위 큐는 우선순위가 기준이라는 것이 차이점이다.
• 우선순위 큐를 구현하는 방법에는 여러가지가 있지만, 보통 완전이진트리를 기반으로하는 힙(Heap)을 이용하여 구현한다.

 

 

 

 

 

1-1. 우선순위큐 구현방법 별 시간복잡도 비교

• 우선순위 큐를 힙으로 구현할 경우, 삽입과 삭제 모두 O(logn)에 가능하다는 이점이 있다!!

 

 

 

 

 

 

1-2. 완전이진트리(Complete Binary Tree)

• 트리의 한 종류. 우선순위큐를 구현하기 위한 힙 자료구조의 기반이 되는 개념이다.
• 조건 1) 완전: 반드시 자식 노드가 왼쪽에서부터 오른쪽으로 채워져야한다. 왼쪽 자식노드 없이 오른쪽 자식노드만 가질 수 없다.
• 조건 2) 이진: 자식 노드를 0~2개 갖는다. 이진트리이므로 자식노드를 최대 2개까지 갖는 트리이다.
• 조건 3) full: 마지막 레벨을 제외한 다른 레벨은 반드시 노드가 가득 차있어야 한다.

 

 

 

 

 

1-3. 힙(Heap)

• 최대값과 최소값을 시간복잡도 O(logn)에 검색, 반환할 때 사용!!
• 힙 외에 가장 큰 or 작은 값을 찾기 위한 방법 중 정렬은 O(nlogn)이고 max(), min() 함수는 O(n)이기에 힙 자료구조를 사용하면 O(logn)로 시간복잡도 단축이 가능하다!
• 완전이진트리를 기반으로 구현
• 추상적 자료구조(물리적인 데이터 저장방법 X)인 힙이 실제적으로 저장되는 자료구조는 배열(파이썬에선 리스트)이다.
• 힙 자료구조는 max heap과 min heap 두 가지가 있다.
• Max heap: 부모노드가 자식노드보다 반드시 크거나 같다.
• Min heap: 부모노드가 자식노드보다 반드시 작거나 같다.
• Max heap의 경우 루트 노드에 항상 가장 큰 값이 위치하고, Min heap의 경우 항상 루트 노드에 가장 작은 값이 위치한다. Heap에다가 어떤 값을 push하면 내부적으로 자동으로 정렬된다(느슨한 정렬).

 

 

 

 

 

 

2. heapq 모듈

• 파이썬에서 우선순위 큐 구현을 위해 쓰이는 모듈. 'import heapq'를 통해 임포트
• heapq 모듈은 파이썬의 리스트를 기반으로 구현된다
• heapify 메서드를 사용할 경우 기본적으로 최소 힙으로 구현(최대 힙은 별도의 트릭 사용)
• 배열(리스트)에 저장된 요소들이 우선순위(값)에 따라 느슨한 정렬이 된다. 그렇기에 Min heap의 경우 항상 가장 작은 값이 루트 노드에 위치하게 되고, Max heap의 경우 항상 가장 큰 값이 루트노드에 위치하게 된다.

# heapq 모듈 임포트
import heapq

 

 

 

 

2-1. heaqp 모듈 주요 메서드

• heapq.heapify(x): 리스트 `x`를 최소 힙으로 변환. 이 작업은 O(N) 시간에 수행된다. 여기서 N은 리스트의 길이이다(빈 리스트일 경우 .heapify 메서드를 생략하고 바로 .heappop이나 .heappush 메서드 사용 가능)
• heapq.heappush(heap, item): `item`을 이미 힙인 `heap`에 추가한다. 시간 복잡도는 O(log N)
• heapq.heappop(heap): 힙에서 가장 작은 항목을 팝하고 반환한다. 만약 힙이 비어있을 경우, `IndexError`를 발생. 이 연산의 시간 복잡도 역시 O(log N)

import heapq

# 힙 생성 및 요소 추가
nums = [1, 5, 7, 2, 6, 8]
heapq.heapify(nums)  # nums를 힙으로 변환
print(nums)    # [1, 2, 7, 5, 6, 8] 출력(heapify된 상태. 이제 heaqpush 및 heappop 가능)

# 힙에 새로운 요소 추가
heapq.heappush(nums, 10)
print(nums)   # [1, 2, 7, 5, 6, 8, 10] 출력(이 리스트를 트리 형태로 생각해보면 힙 규칙에 따라 느슨하게 정렬 됨)

# 힙에서 가장 작은 요소 제거 및 반환
print(heapq.heappop(nums))
print(nums)    # 1 출력
print(nums)    # 2 출력
print(nums)    # 5 출력
print(nums)    # 6 출력

# 남은 요소 확인
print(nums)    # [7, 8, 10] 출력

 

 

 

References

https://velog.io/@dlgosla/CS-%EC%9E%90%EB%A3%8C%EA%B5%AC%EC%A1%B0-%EC%9D%B4%EC%A7%84-%ED%8A%B8%EB%A6%AC-Binary-Tree-vzdhb2sp

[CS - 자료구조] 이진 트리 (Binary Tree) 개념과 종류

https://velog.io/@yeonjin1357/%EC%95%8C%EA%B3%A0%EB%A6%AC%EC%A6%98-%ED%9E%99Heap-%EC%9E%90%EB%A3%8C%EA%B5%AC%EC%A1%B0

[알고리즘] 힙(Heap) 자료구조

https://levelup.gitconnected.com/visualize-design-and-analyse-the-priority-queue-data-structure-a10a07ecd14a

Visualize, Design, and Analyse the Priority Queue Data Structure

 

https://suyeon96.tistory.com/31#---%--%ED%-E%--%EC%-D%B-%EB%-E%--%-F