201221 개발일지(14일차) - 스택과 큐(3) : 오늘은 우선순위 큐(Priority Queue) + 파이썬에서 heapq로 우선순위 큐 구현하기

우선순위 큐(Priority Queue)란?

큐의 기본개념에서 각 원소마다 우선순위가 추가되어, 원소들의 우선순위가 높은 것부터 Dequeue를 진행하는 자료구조다.

파이썬에서의 우선순위 큐 활용을 위한 힙큐(heapq) 모듈!

힙(heap)이란 원래 완전이진트리(complete binary tree)를 기본으로 한 자료구조다.

• 힙의 특성 : 부모-자식 노드의 키값 대소 관계가 일정하게 유지된다.

1. 최대 힙 : 부모 노드의 키 값이 자식 노드의 키 값보다 항상 큰 힙
2. 최소 힙 : 부모 노드의 키 값이 자식 노드의 키 값보다 항상 작은 힙: 최소 힙의 예

파이썬에서의 힙큐 모듈은 최소 힙 자료구조를 제공한다.

heapq모듈은 내장 모듈이며, import하여 사용할 수 있다.

import heapq

최소 힙 생성

파이썬에서 최소 힙 생성은 따로 없으며, 그냥 List를 생성하여 이를 활용하면 된다.

heap = []

힙 원소 추가(heappush)

최소 힙 정렬을 유지하면서 원소를 추가할 수 있다.

힙 원소 삭제(heappop)

최소 힙에서는 가장 작은 값이 정렬 맨 앞에(트리 맨 위에) 올라오는데, 최소 힙 정렬을 유지하면서 원소를 삭제할 수 있다. 즉, 정렬 맨 앞의(트리 맨 위의) 값이 삭제 되면서 트리가 재배치 된다.

기존에 원소가 있는 List를 힙으로 만드는 heapify() 함수

아래 예시와 같이 heapify() 함수를 활용하면 기존의 List도 최소 힙 정렬을 유지하는 힙(리스트)로 만들 수 있다.

list = [4, 1, 7, 3, 8, 5]
heapq.heapify(list)
print(list)

출력값
>>> [1, 3, 5, 4, 8, 7]

파이썬 Heapq에 대해 잘 정리해 둔 Link : https://www.daleseo.com/python-heapq/