Java - Priority Queue

Priority Queue(우선순위 큐)란?

우선 순위에 따라 데이터가 추출되는 구조로 들어간 순서에 상관없이 우선 순위가 높은 데이터가 먼저 추출된다.

 

Priority Queue를 구현하는 방법

• 배열로 구현
• 연결 리스트로 구현
• Heap으로 구현

 

배열로 구현하는 방법

구현은 간단하지만 데이터 삽입 및 삭제가 일어날 때마다 연산의 횟수가 많아지는 단점이 있다. 또한 들어오는 데이터의 삽입 위치를 결정하기 위해 저장된 모든 데이터들과 우선 순위를 비교해야 하는데, 최악의 경우 우선 순위가 가장 낮은 데이터가 들어오면 큐의 모든 원소와 우선 순위를 비교해야 하는 일이 발생한다.

 

연결 리스트로 구현하는 방법

배열보다 삽입, 삭제가 용이하지만 역시나 삽입 위치를 결정해야 하므로 저장된 원소들과의 우선 순위 비교가 이루어져야 한다. 노드 수가 많아질수록 성능은 저하된다.

 

Heap으로 구현하는 방법

배열과 연결 리스트로 구현하는 방법 모두 성능이 좋지 않으므로 주로 Heap을 이용하여 Priority Queue를 구현한다.

 

Priority Queue의 특징

• 값을 비교해야 하므로 null값을 허용하지 않음
• 비교할 수 없는 객체는 큐를 만들 수 없음
• 내부구조는 이진트리 힙으로 구성되어 있음
• add() 및 poll()에 O(log(n))의 시간이 걸림
• AbstractQueue, AbstractCollection, Collection 및 Object 클래스에서 메소드를 상속함

---

Priority Queue 선언

PriorityQueue<타입> 변수명 = new PriorityQueue<>();

 

기본적으로 낮은 순으로 우선순위가 결정되고, 반대로 높은 순으로 우선순위를 결정하고 싶다면 Collections.reverseOrder() 메소드를 사용하면 된다.

---

Priority Queue 값 추가, 삭제

추가 메소드 : add(), offer()

add() 메소드는 Collection 클래스에서 가져오는 메소드이고, offer() 메소드는 Queue() 클래스에서 가져오는 메소드이다.

 

값을 추가하면 우선순위 큐만의 정렬방식으로 정렬이 되는데, 그 형태는 이진트리로 구성된다. 삽입한 값이 이진트리의 가장 오른쪽 아래로 삽입되는데, 그 수가 부모와 비교하여 부모보다 작은 값인 경우 부모와 위치를 스왑하고, 그렇지 않으면 스왑하지 않는다.

 

삭제 메소드 : poll(), remove(), clear()

poll(), remove() 메소드는 우선순위가 가장 높은 값을 제거하고, remove(int index)는 index 순위에 해당하는 값을 제거한다. clear() 메소드를 사용하면 큐의 모든 값을 삭제한다.

 

우선순위가 가장 높은 값을 삭제하게 되면, 우선 삭제할 노드의 값(우선순위가 가장 높은 값, 루트 노드)과 마지막 노드의 값(우선순위가 가장 낮은 값)이 스왑된다. 루트 노드를 제거하고, 스왑된 노드(우선순위가 가장 낮았던 값)와 그 자식노드를 비교하여 그 중 더 작은 값이 부모노드로 올라온다.

---

Priority Queue 크기 구하기

size() : Priority Queue의 개수를 구할 수 있다.

---

Priority Queue 값 출력하기

peek() : 우선순위가 가장 높은 값을 출력한다.

 

전체 큐의 값을 가져오려면 Iterator 메소드를 가져와 사용한다.

예)

[...]
	PriorityQueue<Integer> pq = new PriorityQueue<>();

	Iterator iterator = pq.iterator();
	while(iterator.hasNext())
		System.out.print(iterator.next() + " ");
[...]

---

Priority Queue의 우선 순위 기준 부여하기

• java.lang.Comparable<T> : 원소 스스로 다른 원소와 자신을 비교할 때 사용하는 방법
• java.util.Comparator<T> : 두 개의 원소 대소 비교를 비교자가 판단하는 방법

java.lang.Comparable<T>

 

※ int compareTo(T other)

 

[자기 자신] - [other] 형태

• 음수 : [자기 자신] < [other] 인 경우로 앞이 더 작다는 것을 의미. 오름차순으로 만들고 싶을 때 
• 0 : [자기 자신] = [other] 인 경우
• 양수 : [자기 자신] > [other] 인 경우로 앞이 더 크다는 것을 의미. 내림차순으로 만들고 싶을 때

java.util.Comparator<T>

 

※ int compare(T o1, T o2)

 

[o1 - o2] 형태

• 음수 : [o1] < [o2] 인 경우로 앞이 더 작다는 것을 의미. 오름차순으로 만들고 싶을 때 
• 0 : [o1] = [o2] 인 경우
• 양수 : [o1] > [o2] 인 경우로 앞이 더 크다는 것을 의미. 내림차순으로 만들고 싶을 때

 

---

참조
https://crazykim2.tistory.com/575
https://devje8.tistory.com/18