Priority Queue Algorithm 설명

Priority Queue

이번시간에는 PriorityQueue에 대해서 알아보도록 하겠습니다.

PriorityQueue란 우선순위 큐로써 일반적인 큐의 구조 FIFO(First In First Out)를 가지면서,

FIFO로 데이터가 들어온 순서대로 데이터가 나가는 것이 아닌 우선순위를 먼저 결정을 하고 결정한 우선순위로 출력이 되는 것을 의미합니다.

 

PriorityQueue를 사용하기 위해선 우선순위 큐에 저장할 객체는 필수적으로 Comparable Interface를 구현해야 합니다.

 

Comparable Interface를 구현하면 compareTo method를 오버라이드하게 되고,

해당 객체에서 처리할 우선순위 조건을 리턴해주면 PriorityQueue 가 알아서 우선순위가 높은 객체를 추출해줍니다.

 

PriorityQueue는 Heap(힙)을 이용하여 구현하는 것이 일반적입니다.

 

데이터를 삽입할 때 우선순위를 기준으로 최대/최소 힙을 구성하고 데이터를 꺼낼 때 루트(상단) 노드를 얻어낸 뒤,

루트 노드를 삭제할 때는 빈 루트 노드 위치에 맨 마지막 노드를 삽입한 후 아래로 내려가면서 적절한 자리를 찾아 옮깁니다.

 

최대 값이 우선순위인 큐 = 최대 힙,

최소 값이 우선순위인 큐 = 최소 힙

 

Priority Queue 특징

1. 우선순위 중에서 높은 우선순위를 먼저 꺼냅니다.
   우선순위 큐에 들어가는 원소는 비교가 가능한 기준이 있어야 한다.
   즉, 재정의를 해야겠죠? (compareTo)
2. 내부 요소는 힙으로 구성되어 이진트리 구조입니다.
3. 내부구조가 힙으로 구성되어 있기에 시간 복잡도는 O(NLogN)입니다.
4. 우선순위를 중요시해야 하는 상황에서 주로 쓰입니다.
5. 큐의 공간이 없을 때에는 Exception이 일어날 수 있습니다. 

 

Priority Queue 선언

Priority Queue를 사용하려면 java.util.PriorityQueue를 import 해야 한다.

import java.util.PriorityQueue;
import java.util.Collections;

//낮은 숫자가 우선 순위인 int 형 우선순위 큐 선언
PriorityQueue<Integer> priorityQueueLowest = new PriorityQueue<>();

//높은 숫자가 우선 순위인 int 형 우선순위 큐 선언
PriorityQueue<Integer> priorityQueueHighest = new PriorityQueue<>(Collections.reverseOrder());

 

Priority Queue 동작

Priority Queue에 값 삽입 : add, offer

// add(value) 메서드의 경우 만약 삽입에 성공하면 true를 반환, 
// 큐에 여유 공간이 없어 삽입에 실패하면 IllegalStateException을 발생
priorityQueueLowest.add(1);
priorityQueueLowest.add(10);
priorityQueueLowest.offer(100);

priorityQueueHighest.add(1);
priorityQueueHighest.add(10);
priorityQueueHighest.offer(100);

 

Priority Queue 값 삭제 : poll(), remove()

priorityQueue.poll();       // priorityQueue에 첫번째 값을 반환하고 제거 비어있다면 null
priorityQueue.remove();     // priorityQueue에 첫번째 값 제거
priorityQueue.clear();      // priorityQueue에 초기화

값을 제거할 시 우선순위가 가장 높은 값이 제거됩니다.

poll() 함수는 우선순위 큐가 비어있으면 null을 반환합니다. 

pop을 하면 가장 앞쪽에 있는 원소의 값이 아래 그림과 같이 제거됩니다.

queue의 모든 요소를 제거하려면 clear() 메서드를 사용합니다.

 

 

각 구현 방식에 시간복잡도는 다음과 같습니다. (*n은 노드의 수입니다)

구현 방법	enqueue()	dequeue()
배열 (unsorted array)	O(1)	O(N)
연결 리스트 (unsorted linked list)	O(1)	O(N)
정렬된 배열 (sorted array)	O(N)	O(1)
정렬된 연결 리스트 (sorted linked list)	O(N)	O(1)
힙 (heap)	O(logN)	O(logN)

 

힙(heap)이란?

1. 힙을 저장하는 표준적인 자료구조는 배열 입니다.
2. 구현을 쉽게 하기 위하여 배열의 첫 번째 인덱스인 0은 사용되지 않습니다.
3. 특정 위치의 노드 번호는 새로운 노드가 추가되어도 변하지 않습니다.
-힙에서의 부모 노드와 자식 노드의 관계
왼쪽 자식의 인덱스 = (부모의 인덱스) * 2
오른쪽 자식의 인덱스 = (부모의 인덱스) * 2 + 1
부모의 인덱스 = (자식의 인덱스) / 2

 

<참고 자료>
https://gmlwjd9405.github.io/2018/05/10/data-structure-heap.html

[자료구조] 힙(heap)이란 - Heee's Development Blog

 

 

그럼 지금까지 Priority Queue에 대한 설명이었습니다.

 

감사합니다.