[Python] 비선형 자료구조 - 우선순위 큐와 힙(feat. heapq 라이브러리)

우선순위 큐란, 우선순위가 높은 원소가 먼저 출력되는 추상적 자료형을 의미한다.

비선형 구조를 갖는 자료구조인데, 배열이나 연결 리스트로도 구현할 수 있지만 출력과 원소를 찾고 삭제하는 과정 등이 비효율적이기 때문에, 보통은 힙(Heap)을 통해 구현한다.

그리고 파이썬에서는 heapq 라이브러리를 이용해서 힙의 연산을 이용할 수 있다.

 

1. 힙(Heap)

최소 힙 예시

우선, 힙이란 완전 이진 트리(Complete Binary Tree)이고, 모든 노드에 저장된 값들은 자식 노드들의 값보다 작거나 같다. 여기서 값의 크기가 작을수록 큰 우선순위를 부여하는 것이라고 생각하면 된다.

즉, 배열을 정렬했을 때 기본적으로 오름차순 정렬되는 것처럼 일반적인 힙에서는 루트 노드(우선순위가 가장 높은 노드)가 값이 가장 작다.

이런 특징 때문에 기본적으로 힙은 최소 힙의 성격을 갖고, 최대 힙을 구현할 때는 저장하는 값을 음수로 바꾸거나 다른 과정을 거쳐야 한다.

 

2. 힙의 종류

1) 최소 힙(Min Heap): 부모 노드는 항상 자식 노드보다 작은 값을 갖고 있는 힙

2) 최대 힙(Max Heap): 부모 노드는 항상 자식 노드보다 큰 값을 갖고 있는 힙

 

3. Heapq 라이브러리 이용

heappush로 자료 추가, heappop으로 우선순위가 가장 큰 원소 삭제 및 반환의 연산이 가능하다.

import heapq

myList = []
heapq.heappush(myList, 7)  # myList: [7]
heapq.heappush(myList, 1)  # myList: [1, 7] - 최소 힙 형태를 띄기 때문에 1이 맨 앞으로 저장됨.
heapq.heappop(h)  # 1