우선순위 큐 (Priority Queue)

한마디로 정의

사용자가 지정한 우선순위가 높은 원소가 먼저 처리되는 자료구조야. ( 큐는 알지? )

 

 

설명

어떻게보면 그냥 큐는 시간이 우선순위여서 먼저 Insert된 원소가 먼저 pop (FIFO)가 되지.

하지만 우선순위 큐는 사용자가 지정한 우선순위에 의해 높은 우선순위가 먼저 pop 돼.

( 긴급한 환자가 먼저 치료 받는 것을 떠올리면 돼 )

 

List는 LinkedList와 ArrayList로 구현할 수 있는거와 같이

 

우선순위 큐도

 1. ArrayList

 2. LinkedList

 3. Heap

 

3가지 자료구조를 이용해서 구현이 가능해

 

1. ArrayList의 경우

  1. 데이터의 삽입 과정에서 데이터를 한 칸씩 당기거나 밀어야 하는 연산을 계속해야해

  2. 삽입의 위치를 찾기 위해 배열에 저장된 모든 데이터와 우선순위를 비교해야해

 왜냐하면 우선순위에 따라 pop을 해야하는데 Head에 해당하는 원소가 우선순위가 높아야 하므로, 다른 원소가 추가될 때 그 원소의 우선순위가 해당하는 위치에 넣고 데이터를 Shift해야하기 때문이야

그래서 우선순위가 가장 낮은 데이터를 삽입할 때 최악의 경우가 발생하지

 

 1개의 데이터에 대해서

  삽입의 시간 복잡도 : O(N)

  삭제의 시간 복잡도 : O(1)  

추가로 shift 연산의 시간이 걸릴거야

 

 결론! ArrayList도 효율이 떨어진다!

 

2. LinkedList의 경우

  ArrayList의 경우의 첫번째 문제점은 해결가능 하지만 이 타입으로 만들 경우 한가지 문제점이 있어

 1. 삽입의 위치를 찾기 위해 첫번째 노드에서 부터 시작해 마지막 노드에 저장된 데이터와 우선순위를 비교해가며 Insert해야할거야. 하지만 데이터가 많아질 때 노드의 수에 비례해서 성능이 저하되지.

 1개의 데이터에 대해서

  삽입의 시간 복잡도 : O(N)

  삭제의 시간 복잡도 : O(1)

 

 결론! LinkedList도 효율이 떨어진다!

 

3. Heap 경우

 Heap은 최댓값 및 최솟값이 루트노드에 있기 때문에 가장 우선순위가 높은 원소를 빠른 시간에 꺼낼 수 있어. 그래서 이 자료구조를 이용해서 우선순위 큐 자료구조를 구현하면 무척 빨라

 Heap에 대해 더 알고 싶다면 여기를 클릭해 https://i5i5.tistory.com/33

 1개의 데이터에 대해서

  삽입의 시간 복잡도 : O(logN)

  삭제의 시간 복잡도 : O(logN)

 

 결론! Heap 자료구조를 이용하자!

 

어디에 쓰이냐고?

  다익스트라 알고리즘에서 최소 정점을 찾기위해 이 우선순위 큐를 쓰면 더 빠르게 최단거리를 구할 수 있어

 이 알고리즘에 우선순위 큐를 적용한 것이 Prim 알고리즘이야

 

 

 

 

package samsung;

import java.util.PriorityQueue;

class Student implements Comparable<Student> {
	String name;
	int age;
	
	public Student() {
		super();
	}
	public Student(String name, int age) {
		super();
		this.name = name;
		this.age = age;
	}
	@Override
	public int compareTo(Student o) {
		return this.age - o.age;
	}
	@Override
	public String toString() {
		return "Student [name=" + name + ", age=" + age + "]";
	}
}

public class priorityQ {
	public static void main(String[] args) {
		PriorityQueue<Student> pq = new PriorityQueue<Student>();
		
	    pq.offer(new Student("전우형", 2));
	    pq.offer(new Student("이정연", 9));
	    pq.offer(new Student("박다솜", 6));
	    pq.offer(new Student("김재룡", 7));
	    pq.offer(new Student("이근희", 4));
	    pq.offer(new Student("홍휘진", 9));

	    while (!pq.isEmpty())
	        System.out.println(pq.poll().toString());
	} // end of main
} // end of class