[자료구조] Priority Queue(우선 순위 큐)

 

 

다룰 내용

• Priority Queue란 무엇인가?
• Priority Queue 구현 방법
• PrioriyQueue의 우선 순위 기준 부여하기(Java) - Comparable, Comparator

---

 

Priority Queue란 무엇인가?

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

 

 

Prioriy Queue를 구현하는 방법

• 배열로 구현하는 방법
• 연결 리스트로 구현하는 방법
• Heap을 이용하는 방법

 

 

배열로 구현하는 방법

구현하는 방법은 간단하나 데이터 삽입 및 삭제가 일어날 때마다 당기거나 미는 연산을 계속해서 연산이 많다는 단점이 있습니다. 또한 들어오는 데이터의 삽입 위치를 결정하기 위해 저장되어 있는 모든 데이터들과 우선 순위를 비교해야 합니다. 이때 최악의 경우 들어오는 데이터가 가장 우선 순위가 낮을 때 결국 모든 원소와 전부 비교를 하기 때문에 이러한 경우가 빈번할 수록 수행 시간이 증가됩니다.

 

 

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

배열보다 삽입, 삭제가 용이하기 때문에 배열로 구현하는 경우보다 조금은 유리합니다. 그러나 역시나 삽입 위치를 결정해야 하기 때문에 저장된 원소와의 비교는 배열과 동일한 단점입니다. 노드 수가 많아질 수록 비교 대상이 증가하므로 성능이 저하된다는 단점이 있습니다.

 

 

Heap을 이용하는 방법

위의 두 가지 방법 모두 원소의 수가 많아질 수록 성능이 저하되기 때문에 주로 Heap을 이용해서 Priority Queue를 구현합니다. 

 

 

---

 

PrioriyQueue의 우선 순위 기준 부여하기(Java)

Java의 util 패키지에 있는 PriorityQueue도 마찬가지로 Heap을 이용하여 구현되어 있습니다.

 

PriorityQueue를 이용할 때 우선 순위 기준을 부여하는 방법은 두 가지가 있습니다.

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

 

java.lang.Comparable<T>

int compareTo(T other) : 비교, 판단 결과를 int 형으로 줌.

 

자기 자신 - other 형태

음수 : 자기 자신(10) - other(12)인 경우 -2 반환, 앞이 더 작다는 의미입니다. (오름차순으로 만들고 싶을 때)

0 : 두 개의 원소가 같은 경우

양수 : 자기 자신(12) - other(10)인 경우 2 반환, 앞이 더 크다는 의미입니다. (내림차순으로 만들고 싶을 때)

 

package basic;

import java.util.PriorityQueue;

public class Compare {
	
	public static class Student implements Comparable<Student> {
		int num;
		String name;
		
		public Student(int num, String name) {
			this.num = num;
			this.name = name;
		}

		@Override
		public int compareTo(Student o) {
			return this.num - o.num;
		}

		@Override
		public String toString() {
			return "Student [num=" + num + ", name=" + name + "]";
		}
	}

	public static void main(String[] args) {
		PriorityQueue<Student> pq = new PriorityQueue<Student>();
		
		pq.offer(new Student(4, "강동원"));
		pq.offer(new Student(1, "송중기"));
		pq.offer(new Student(3, "현빈"));
		pq.offer(new Student(2, "유연석"));
		
		System.out.println(pq.poll());
		System.out.println(pq.poll());
	}
}

 

poll한 결과(정상 수행)

 

java.util.Comparator<T>

int compare(T o1, T o2)

 

o1 - o2 형태

음수 : o1(10) - o2(12)인 경우 -2 반환, 앞이 더 작다는 의미입니다. (오름차순으로 만들고 싶을 때)

0 : 두 개의 원소가 같은 경우

양수 : o2(12) - o1(10)인 경우 2 반환, 앞이 더 크다는 의미입니다. (내림차순으로 만들고 싶을 때)

 

package basic;

import java.util.Comparator;
import java.util.PriorityQueue;

public class Compare {
	
	public static class Student {
		int num;
		String name;
		
		public Student(int num, String name) {
			this.num = num;
			this.name = name;
		}

		@Override
		public String toString() {
			return "Student [num=" + num + ", name=" + name + "]";
		}
	}
	
	public static class MyComparator implements Comparator<Student> {
		@Override
		public int compare(Student o1, Student o2) {
			return o1.num - o2.num;
		}
	}

	public static void main(String[] args) {
		PriorityQueue<Student> pq = new PriorityQueue<Student>(new MyComparator());
		
		pq.offer(new Student(4, "강동원"));
		pq.offer(new Student(1, "송중기"));
		pq.offer(new Student(3, "현빈"));
		pq.offer(new Student(2, "유연석"));
		
		System.out.println(pq.poll());
		System.out.println(pq.poll());
	}
}

 

poll한 결과(정상 수행)

 

 

그렇다면 어떻게 사용해야하는가?

원소 스스로 비교할 수 있다면 Comparable을 implements해서 사용할 수 있습니다.

primitive 타입을 객체화한 Integer, String, Character 등은 이미 비교 기준을 이미 가지고 있기 때문에 비교 기준을 바꾸려면 Comparator를 써서 확장을 해주어야 합니다.

 

PriorityQueue뿐만 아니라 정렬이 필요한 순간에 마찬가지로 Comparable과 Comparator를 사용할 수 있습니다.