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

우선순위 큐(Priority Queue)

• 일반적인 큐(Queue)는 먼저 들어간 데이터가 먼저 나오는 FIFO(First in First Out) 구조로 저장하는 선형 자료구조이다.
• 우선순위 큐(Priority Queue)는 들어간 순서에 상관없이 우선순위가 높은 데이터가 먼저 나오는 것을 말한다.
• 힙 방식이 최악의 경우에도 O(logN)을 보장하기 때문에 일반적으로 힙으로 구현한다.

💡 우선순위 큐는 왜 배열로 구현하지 않을까?

• 우선순위가 높은 순서대로 넣는다면, 우선순위가 높은 데이터를 반환하는 것은 맨 앞의 인덱스를 이용하면 되므로 어렵지 않다.
• 하지만 우선순위가 중간인 것이 들어가야하는 삽입 과정에서는 뒤에 데이터까지 모두 한 칸씩 뒤로 밀어야한다.
• 최악의 경우 삽입해야하는 위치를 찾기 위해 모든 인덱스를 탐색해야한다.
• 시간복잡도 : 삭제 O(1), 삽입 O(n)

💡 우선순위 큐는 왜 배열로 구현하지 않을까?

• 우선순위가 높은 순선대로 연결시키면, 우선순위가 높은 데이터를 반환하는 것은 쉽다.
• 하지만 삽입 과정에서는 그 위치를 찾아야하고, 최악의 경우 삽입해야하는 위치를 찾기 위해 맨 끝까지 가게 된다.
• 시간 복잡도 : 삭제 O(1), 삽입 O(n)

Priority Queue 선언

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

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

Priority Queue 값 추가하기

PriorityQueue<Integer> pq = new PriorityQueue<>();
	// 1, 15, 8, 21, 25, 18, 10 값 추가
	pq.add(1);		pq.add(15);		pq.offer(10);
	pq.add(21);		pq.add(25);		pq.offer(18);
	pq.add(8);

Priority Queue 크기 구하기

System.out.println(pq.size());

Priority Queue 값 삭제하기

pq.poll(); //우선순위가 가장 높은 값을 반환하고 제거
pq.remove(); //우선순위가 가장 높은 값 제거
pq.remove(1); //index 순위에 해당하는 값을 제거

Priority Queue 값 출력하기

System.out.println(pq.peek()); //우선순위가 가장 높은 값 출력
		
Iterator iterator = pq.iterator(); //Iterator 메소드 사용하여 출력
while(iterator.hasNext())
	System.out.print(iterator.next() + " ");