[JAVA] PriorityQueue : 우선순위 큐

목차

우선순위 큐?

• GREEDY알고리즘 문제는 정렬 아니면 우선순위 큐 문제일 정도로 자주 쓰이는 자료구조.
• 일반적인 QUEUE처럼, 데이터가 들어온 순서대로 나가는 것이 아니라, 우선순위가 높은 데이터가 먼저 출력되는 자료구조.
• 우선순위 큐는 힙으로 구현 가능한데, 최소값 우선큐 = 최소힙 & 최대값 우선큐 = 최대힙
• O(logn) 의 시간복잡도

 

알고리즘

삽입 알고리즘

큐에 값이 삽입되면 다음과 같이 진행된다

출처 : [Java] PriorityQueue(우선순위 큐) 클래스 사용법 & 예제 총정리[코딩팩토리]

 

삭제 알고리즘

출처 : [Java] PriorityQueue(우선순위 큐) 클래스 사용법 & 예제 총정리[코딩팩토리]

 

활용

선언

import java.util.PriorityQueue;
import java.util.Collections;
// 선언
PriorityQueue< [자료 타입] > [변수명] = new PriorityQueue<>(); 

-- 예시 
// int 타입 + 낮은 숫자가 우선순위를 가지는 큐 
PriorityQueue<Integer> queue = new PriorityQueue<>(); 

// int 타입 + 큰 숫자가 우선순위를 가지는 큐 
PriorityQueue<Integer> largest_queue = new PriorityQueue<>(Collections.reverseOrder()); 

 

삽입 : add ( ) , offer( )

queue .add(1);
queue .add(2);
queue .offer(3);

largest_queue .add(1);
largest_queue .add(2);
largest_queue .offer(3);

 

삭제 : poll( ), remove( ) , clear( )

// 현재 큐에 상태 = [1,2,3]

// 첫번째 값을 반환후 제거. 비어있다면 null (pop과 비슷) 
queue .poll();    // 1반환  (1,2,3) 순으로 반환 
largest_queue .poll();    // 3반환 (3,2,1) 순으로 반환

// 첫번째 값 제거. 큐가 비어있다면 예외 발생
queue .remove(); 
queue .remove(int Index) // Index 순위에 해당하는 값을 제거

// 초기화
queue .clear();

 

참조( 반환O, 제거 x ) : peek( ) , element( )

// 첫번째 값을 참조. 큐가 비어있다면 null을 반환
queue .peek();   

// 첫번째 값을 참조. 큐가 비어있다면 예외 발생
queue .element();  

 

크기 : size( )

queue .size();   // 3 반환

 

Priority Queue 값 출력

System.out.print(lowest_queue);
---
Iterator iterator = lowest_queue .iterator();
while(iterator.hasNext())
	System.out.print(iterator.next() + " ");

 

참조 

[JAVA] Priority Queue(우선순위 큐) 개념 및 사용법 정리 (tistory.com)

https://velog.io/@gillog/Java-Priority-Queue%EC%9A%B0%EC%84%A0-%EC%88%9C%EC%9C%84-%ED%81%90