[자료구조] 우선순위 큐(Priority Queue)에 대해 알아보자!(+Python 구현)

📚 목차

1.  우선순위 큐(Priority Queue)란?
2.  힙(Heap) 자료구조
    2.1.  힙 자료구조란?
    2.2.  우선순위 큐 구현 방식: 리스트 vs 힙
3.  힙 기반의 우선순위 큐 구현(Python)
    3.1.  heapq 라이브러리 소개
        3.1.1.  힙 원소 추가(heappush)
        3.1.2.  힙 원소 삭제(heappop)
        3.1.3.  리스트를 힙으로 변경(heapify)
    3.2.  힙 기반의 우선순위 큐 구현 예시

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

우선순위 큐는 말 그대로 우선순위가 가장 높은 데이터를 가장 먼저 추출하는 자료구조입니다. 일반적으로 큐(Queue) 자료구조는 선입선출 방식으로서 가장 먼저 삽입된 데이터를 가장 먼저 추출합니다. 간단하게 특징이 유사한 자료구조들의 데이터 추출 방식에 대해 비교해 보겠습니다.

자료구조	데이터 추출 방식	예시
스택(Stack)	선입후출: 가장 먼저 삽입된 데이터가 마지막에 추출되는 방식	박스 쌓기(가장 위에 쌓은 박스부터 추출)
큐(Queue)	선입선출: 가장 먼저 삽입된 데이터가 가장 먼저 추출되는 방식	줄 서기(먼저 온 사람이 먼저 입장)
우선순위 큐(Priority Queue)	우선순위가 가장 높은 데이터가 가장 먼저 추출되는 방식	저렴한/비싼 가격 순으로 데이터 추출

스택과 큐 자료구조에 대한 내용은 아래 링크를 참고해 주세요!

heytech.tistory.com/46

[자료구조] 스택(Stack)에 대해 알아보자(+ Python)

heytech.tistory.com/54

[자료구조] 큐(Queue)에 대해 알아보자(+ Python)

다시 우선순위 큐에 대한 설명으로 돌아오면, 우선순위 큐는 우선순위를 지정하여 사용자가 원하는 순서대로 데이터를 추출하는 방식입니다. 만약 우리가 가격과 제품 정보가 무작위로 담긴 자료구조에서 가격이 저렴한 순서대로 상품 데이터를 추출하고 싶으면 어떻게 해야 할까요? 큐 자료구조는 먼저 삽입된 데이터를 순서대로 꺼내가며 가격 정보를 일일이 확인해야 합니다. 반면, 우선순위 큐를 활용하면 저렴한 가격일수록 높은 우선순위를 부여하여 데이터를 추출할 때, 이 우선순위에 따라 데이터를 추출하기만 하면 되기 때문에 훨씬 효율적으로 동작합니다.

2.  힙(Heap) 자료구조

2.1.  힙 자료구조란?

우선순위 큐를 효율적으로 구현하기 위해서는 힙(Heap) 자료구조에 대해 알아야 합니다. 자세한 내용은 아래 링크를 참고해 주시고, 이번 포스팅에서는 간단하게만 설명드리도록 하겠습니다.

heytech.tistory.com/69

[자료구조] 힙(Heap) 자료구조에 대해 알아보자!(+Python 구현)

힙 자료구조는 가장 높은(또는 가장 낮은) 우선순위의 데이터를 찾기 위해 고안된 완전 이진 탐색(Complete Binary Tree) 기반의 자료구조입니다. 힙 자료구조는 최소 힙(Min Heap)과 최대 힙(Max Heap)으로 총 2가지 종류가 있습니다. 먼저, 최소 힙은 항상 데이터 값이 작을수록 우선순위가 높은 경우의 자료구조이며, 반대로 최대 힙은 항상 데이터 값이 클수록 우선순위가 높은 자료구조입니다. 즉, 최소 힙 자료구조는 부모 노드의 key 값이 자식 노드의 key 값보다 작은 경우입니다.

2.2.  우선순위 큐 구현 방식: 리스트 vs 힙

우선순위 큐를 구현할 때는 리스트를 활용해 간단히 구현하거나 힙 자료구조를 이용할 수 있습니다. 하지만 힙 자료구조를 활용하여 구현했을 때가 리스트를 사용했을 때보다 시간 복잡도 측면에서 훨씬 효율적이기 때문에, 대부분 힙 자료구조를 활용해 우선순위 큐를 구현합니다.

 

데이터 개수가 N개일 때, 리스트 기반 우선순위 큐 구현 시 최악의 경우에 시간 복잡도는 O(N^2)입니다. 반면, 힙 자료구조를 사용하면 최악의 경우에도 시간 복잡도가 O(NlogN)입니다. 힙 자료구조의 경우, N개의 데이터를 삽입하고 우선순위에 맞게 데이터를 탐색하는 과정은 모두 O(logN) 의 연산을 N번 반복하므로 O(NlogN) 만큼의 시간이 소요됩니다. 따라서 전체 연산 횟수는 2NlogN이므로 전체 시간 복잡도는 빅오 표기법에 따라 O(NlogN)입니다. 이처럼 시간 복잡도 측면에서 데이터의 개수가 많아질수록 힙 자료구조를 활용하여 우선순위 큐를 구현했을 때가 리스트를 활용할 때보다 훨씬 효율적이라는 것을 알 수 있습니다.

3.  힙 기반의 우선순위 큐 구현(Python)

위와 같이 시간 복잡도 측면에서 힙 자료구조가 효율적이기 때문에 힙을 중심으로 우선순위 큐를 구현하는 방법에 대해 알아보겠습니다. 사실 파이썬에서는 우선순위 큐 기능을 지원하는 라이브러리로서 PriorityQueue와 heapq이 있기 때문에, 굳이 알고리즘 테스트(대회)에서 힙 자료구조를 활용해 직접 구현할 필요는 없습니다. 단순히 파이썬에서 지원해 주는 라이브러리를 이용하면 됩니다. 특히 heapq이 PriortyQueue에 비해 더욱 빠르게 동작하기 때문에 heapq이 더욱 널리 사용되고 있습니다. 이에 본 포스팅에서는 headq 라이브러리를 활용해 우선순위 큐를 구현하는 방법에 대해 설명드리도록 하겠습니다.

3.1.  heapq 라이브러리 소개

import heapq

먼저, heapq 라이브러리 내 메서드를 소개해 드립니다. heapq 라이브러리는 default로 최소 힙 자료구조를 갖는 것이 특징입니다.

3.1.1.  힙 원소 추가(heappush)

# 힙 이름과 추가할 원소를 각각 입력
heapq.heappush([힙 이름], [추가할 원소])

heappush 메서드를 활용하면 최소 힙 자료구조를 유지하면서 새로운 원소를 추가할 수 있습니다.

3.1.2.  힙 원소 삭제(heappop)

heapq.heappop([힙 이름])

heappop 메서드를 활용하면 최소 힙 자료구조를 유지하면서 우선순위가 가장 높은 원소를 추출합니다.

3.1.3.  리스트를 힙으로 변경(heapify)

heapq.heapify([리스트 이름])

# 예시
list1 = [1, 3, 2, 5, 4]
heapq.heapify(list1)

heapify 메서드를 활용하면 기존에 생성한 리스트를 힙 자료구조로 변경할 수 있습니다.

3.2.  힙 기반의 우선순위 큐 구현 예시

import heapq

# 힙 생성
heap = []

# 힙 내 원소 할당
heapq.heappush(heap, '2')
heapq.heappush(heap, '5')
heapq.heappush(heap, '1')
heapq.heappush(heap, '3')
heapq.heappush(heap, '6')
heapq.heappush(heap, '4')

print(heap) # 결과: ['1', '3', '2', '5', '6', '4']

# 우선순위가 가장 높은 순서대로 원소 출력
for _ in range(len(heap)):
    # 쉼표로 출력 결과 구분
    print(heapq.heappop(heap), end = ' ') # 결과: 1 2 3 4 5 6

위(⬆)와 같이 heap을 생성하고 원소를 추가했습니다. heap은 단순히 리스트를 활용하면 됩니다.

---

포스팅 내용에 오류가 있을 경우 댓글 남겨주시면 감사드리겠습니다.

그럼 오늘도 건강하고 즐거운 하루 보내시길 바랍니다.

고맙습니다 :)