[자료구조] 우선순위 큐(PriorityQueue) 개념 및 코드

 

이번 포스팅에선 우선순위 큐에 대해 알아보겠습니다.

큐, 스택에 대한 이해가 없으신 분은 밑의 포스팅을 먼저 보고 와주시면 감사하겠습니다.

본 포스팅은 python으로 진행합니다.

 

 

[스택 개념 및 코드]

https://mengu.tistory.com/29?category=931463 

[자료구조] 스택(Stack) 개념 및 코드 구현

 

[큐 개념 및 코드]

https://mengu.tistory.com/30?category=931463 

[자료구조] 큐(Queue) 개념 및 코드 구현

 

 

 

 

📌 우선순위 큐(Priority Queue) 개념

스택(Stack)과 큐(Queue)는 데이터가 삽입된 순서에 따라 추출되거나 삭제되었습니다.

하지만 우선순위 큐는 삽입 순서와 상관없이 작동합니다. 이름에 볼 수 있듯, 데이터엔 우선순위가 존재합니다.

사용자가 직접 지정하지 않는 경우, 데이터가 작은 순서대로 우선순위가 매겨집니다. 하지만 사용자가 직접 우선순위를 지정하는 경우, 그 순서대로 데이터가 추출되고 삭제됩니다.

 

 

 

자료에 직접 우선순위를 매길 수 있다는 장점이 있지만, 데이터가 삽입/삭제 될 때마다 정렬을 해줘야 하기에 시간/공간 복잡도는 스택, 큐와 차이를 보입니다.

 

 

 

 

📌 시간 복잡도

O(1)

스택과 큐는 데이터를 하나씩 입력하고 삭제합니다. 따라서 삽입, 삭제의 시간 복잡도가 O(1) 입니다.

 

O(logN)

우선순위 큐는 데이터를 삽입하고 삭제할 때마다 정렬을 진행합니다. 이에 따라 시간 복잡도가 O(logN)입니다.

 

 

 

📌 코드

 

🎨 클래스 임포트

 

우선순위 큐는 파이썬 라이브러리에 구현되어 있습니다.

따라서 import만 해주면 됩니다.

from queue import PriorityQueue

 

 

 

🎨 우선순위 큐 객체 생성

 

우선순위 큐는 하나의 클래스입니다. 클래스를 활용하기 위해선 객체를 생성해야 합니다.

priority_que = PriorityQueue()

 

 

 

🎨 원소 삽입

 

우선순위에 큐는 put() 함수를 통해 원소를 삽입할 수 있습니다.

이렇게 원소를 삽입할 경우, 추출/삭제될 때는 원소의 크기에 따라 순위가 매겨집니다.

priority_que.put(원소)

 

작은 값이 큰 값보다 우선순위가 높습니다.

 

 

 

 

🎨 원소 삽입(튜플 형태)

 

원소를 튜플 형태로 삽입할 수 있습니다.

(우선순위, 원소)

튜플 형태는 사용자가 직접 우선순위를 정해주기 때문에, 명시된 우선순위대로 원소가 반환되거나 삭제됩니다.

priority_que.put((2, "나달"))
priority_que.put((1, "페더러"))
priority_que.put((3, "조코비치"))

 

값을 추출할 경우, 페더러-나달-조코비치 순으로 값이 추출됩니다.

 

 

 

 

🎨 원소 반환 및 삭제

 

get() 함수를 통해 원소를 반환하면서, 큐에선 삭제합니다. 이때 함수에 어떤 인수도 전달하지 않습니다. 

priority_que.get()

 

 

 

📌 예제 코드

예제를 보며 우선순위 큐의 코드 활용을 익혀보겠습니다.

 

 

먼저 클래스를 임포트하고 객체를 생성했습니다.

친구들 리스트를 생성했습니다.

from queue import PriorityQueue

friend_que = PriorityQueue()
friend = ['철수','영희','민수','준영','호병']

 

 

친구들마다 우선순위가 다를 것입니다.

이에 따라 친구를 저장할 때 우선순위를 표기해줍니다.

for i in range(5):
    que.put((i+1, n_list[i]))

 

 

이제 친구 리스트를 뽑아보겠습니다.

1등부터 추출될 것입니다.

for i in range(5):
    print(f'{i+1}순위 : {friend_que.get()[1]}')

 

 

결과

1순위 : 철수
2순위 : 영희
3순위 : 민수
4순위 : 준영
5순위 : 호병

 

 

 

 

지금까지 우선순위 큐에 대해 알아보았습니다.

생각보다 개념도 간단했고, 코드 활용도 쉬웠던 것 같습니다.

이제 실전 문제를 풀어보며 개념을 더욱 탄탄히 하시길 바랍니다.

 

https://www.acmicpc.net/step/13

우선순위 큐 단계