[자료구조 || 알고리즘] 우선순위 큐

우선순위 큐

큐(Queue)는 먼저 들어오는 데이터가 먼저 나가는 FIFO(First In First Out) 형식의 자료구조이다.

우선순위 큐(Priority Queue)는 먼저 들어오는 데이터가 아니라, 우선순위가 높은 데이터가 먼저 나가는 형태의 자료구조이다.

 

우선순위 큐는 일반적으로 힙을 이용한다.

 

힙(Heap)

우선순위 큐를 위해 고안된 완전이진트리 형태의 자료구조.

여러 개의 값 중에서 최대값과 최솟값을 찾아내는 연산이 빠르다.

 

• 최대 힙 (Max Heap)❝ key(부모노드) ≥ key(자식노드) ❞

부모 노드의 키 값이 자식 노드보다 크거나 같은 완전이진트리이다.

출처 https://suyeon96.tistory.com/31

• 최소 힙 (Min Heap)❝ key(부모노드) ≥ key(자식노드) ❞

부모 노드의 키 값이 자식 노드보다 작거나 같은 완전이진트리이다.

출처 https://suyeon96.tistory.com/31

시간 복잡도는 아래와 같다.

출처 https://suyeon96.tistory.com/31

파이썬(Python)

1. 큐 생성

from queue import PriorityQueue

que = PriorityQueue(maxsize = 8)

PriorityQueue 클래스는 queue 내장 모듈에서 제공된다.

우선순위 큐의 디폴트 사이즈는 무한대이기 때문에 만약 특정 크기를 제한 해주고 싶다면 다음과 같이 maxsize를 이용한다.

 

2. 원소 추가

que.put(4)
que.put(1)
que.put(7)
que.put(3)

put을 통해 원소를 추가한다.

 

3. 원소 삭제

print(que.get())  # 1
print(que.get())  # 3
print(que.get())  # 4
print(que.get())  # 7

get을 통해 원소를 삭제한다.

(기본적으로 오름차순으로 진행된다.)

내림차순으로 진행하고 싶다면 -를 붙여주고 나중에 출력할 때 다시 -를 붙여주는 방법을 이용하자.

 

4. 정렬기준 정의

que.put((3, 'Apple'))
que.put((1, 'Banana'))
que.put((2, 'Cherry'))

print(que.get()[1])  # Banana
print(que.get()[1])  # Cherry
print(que.get()[1])  # Apple

(우선순위, 값) 형태로 데이터를 추가하고 제거한다.

 

자바(Java)

1. 큐 생성

import java.util.PriorityQueue;

class Main {
	public static void main(String[] args) {
    
   	PriorityQueue<Integer> que = new PriorityQueue<>();

PriorityQueue 클래스는 내장 모듈에서 제공된다.

 

2. 원소 추가

que.add(4)
que.add(1)
que.offer(7)
que.offer(3)

put, offer을 통해 원소를 추가한다.

 

3. 원소 삭제

print(que.poll())  # 1
print(que.remove())  # 3
print(que.remove(1))  # 4
print(que.poll())  # 7

poll, remove을 통해 원소를 삭제한다.

(기본적으로 오름차순으로 진행된다.)

내림차순으로 진행하고 싶다면 -를 붙여주고 나중에 출력할 때 다시 -를 붙여주는 방법을 이용하자.