우선순위 큐
- 들어간 순서와는 상관없이 높은 우선순위를 가진 원소가 먼저나온다는 특징
- 최소 힙 = 숫자가 작을수록 먼저 나오는 큐
- 최대 힙 = 숫자가 클수록 먼저 나오는 큐
시간 복잡도
- 삽입, 삭제 : O(log n)
선언 방법
new PriorityQueue<[type]>()
// 낮은 수가 우선순위를 가짐
PriorityQueue<Integer> pq = new PriorityQueue<>();
// 높은 수가 우선순위를 가짐
PriorityQueue<Integer> pq = new PriorityQueue<>(Collections.reverseOrder());
// 사전 순으로 더 빨리오는 문자열이 우선순위를 가짐
PriorityQueue<String> pq = new PriorityQueue<>();삽입
add(E element)
- 큐 공간 없어 삽입 실패 시 exception터짐
offer(E element)
- 큐 공간 없어 삽입 실패 시 null 반환
pq.add(3);
pq.add(1);
pq.offer(2); 삭제
poll()
front에 위치한 원소 제거 후 반환
큐 비었다면 null 반환
remove()
front에 위치한 원소 제거 후 반환
큐 비었다면 exception 터짐
pq.poll();
pq.remove();removeIf(Predicate<? super E> filter)
람다 표현식으로 파라미터 전달 가능
필터링 조건
//pq: [1, 2, 3, 4, 5]
pq.removeIf(n -> (n % 2 == 0)); //pq: [1, 3, 5]remove(E element)
- 반환형: boolean
특정 원소 제거
삭제하려는 원소 큐에 없으면 false 반환
removeAll(Collection<?>)
파라미터로 준 컬렉션의 겹치는 원소들 제거
//pq1: [1, 2, 3, 4, 5]
//pq2: [1, 3, 5]
pq1.removeAll(pq2); //p1: [2, 4]
pq1.remove(9); //false접근
peek()
- 반환형: E, queue의 형식
첫 번째 데이터 반환
큐 비어있다면 null 반환
iterator()
-반환형: Iterator
데이터 지우지 않고 순회할 경우 사용
//pq: [1, 3, 2]
Iterator<Integer> iter = pq.iterator();
while(iter.hasNext()) {
Integer i = iter.next();
System.out.print(i + " ");
}출력
1 3 2기타
size()
-반환형: int
toArray()
-반환형: Object[]
큐에 저장된 데이터 배열로 가져옴
for(Object i : pq.toArray()) {
System.out.println(i);
}clear()
우선순위 큐 비우기 (반환값 없음)
우선순위 지정
특정 기준으로 정렬하고 싶거나 큐에 저장된 객체의 어떤 속성으로 정렬하고 싶을 때 다음을 이용한다.
1. implements Comparable
2. Comparator 생성하며 compare함수 오버라이딩
Comparable - compareTo
새로운 클래스를 정의 하고 Comparable을 상속받아 오름차순의 기준을 직접 정의하는 것이다.
compareTo 함수를 오버라이딩 하여 재정의 하면 priorityQueue 를 바로 사용할 수 있다.
public class People implements Comparable<People>{
String name;
int age;
int height;
@Override
public int compareTo(People o) {
// 키로 오름차순 정렬
// 현재 객체가 o보다 작으면 -1, 크면 1 반환
// 동일하면 0 반환
return (this.height > o.height ? 1 : -1);
}
}Comparator - compare
priorityQueue 를 정의 할 때 Comparator를 통해 compare 함수를 오버라이딩 하는 방법이다.
PriorityQueue<People> pq = new PriorityQueue<>(new Comparator<People>() {
@Override
public int compare(People o1, People o2) {
return o1.height > o2.height ? 1 : -1;
}
});
Comparable과 Comparator의 자세한 설명은 아래 링크를 참고하자.
Comparable과 Comparator
정렬 전략 설정
예제 1
숫자 10개를 입력받아 오름차순으로 정렬하되, 홀수가 짝수보다 우선순위가 높다고 가정
import java.util.PriorityQueue;
import java.util.Scanner;
public class priorityQueue {
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
PriorityQueue pq = new PriorityQueue<>((o1, o2) -> {
// 파라미터로 받은 o1, o2는 기본적으로 object 형이기 때문에
// string으로 변환 후, int형으로 다시 변환
int x = Integer.parseInt(o1.toString());
int y = Integer.parseInt(o2.toString());
// x, y가 들어왔을 때, x에 높은 우선순위를 주고싶다면 음수값 return
if(x % 2 == y % 2) {
return x - y;
} else {
if(x % 2 == 1 && y % 2 == 0) {
return -1;
} else {
return 1;
}
}
});
System.out.print("입력 : ");
for(int i = 0 ; i < 10 ; i ++) {
pq.add(sc.nextInt());
}
System.out.print("출력 : ");
for(int i = 0 ; i < 10 ; i ++) {
System.out.print(pq.poll() + " ");
}
}
}
예제 2
Integer 타입만을 받는 Priority Queue가 아닌 (Integer, Integer) 타입으로 받고, 첫번째 인자를 기준으로 정렬하는 예제
import java.util.PriorityQueue;
import java.util.Scanner;
public class PriorityQueueTest {
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
PriorityQueue<MyFormat> pq = new PriorityQueue<>();
System.out.println("입력 x y : ");
for(int i = 0 ; i < 5 ; i ++) {
int x = sc.nextInt();
int y = sc.nextInt();
pq.add(new MyFormat(x, y));
}
System.out.println("출력 x y : ");
for(int i = 0 ; i < 5 ; i ++) {
MyFormat mf = pq.poll();
System.out.println(mf.x + " " + mf.y);
}
}
static class MyFormat implements Comparable<MyFormat>{
int x, y;
public MyFormat(int x, int y) {
this.x = x;
this.y = y;
}
// x를 기준으로 오름차순 정렬
@Override
public int compareTo(MyFormat o) {
return this.x - o.x;
}
}
}참고
https://chb2005.tistory.com/74
https://velog.io/@suk13574/Java-%EC%9A%B0%EC%84%A0%EC%88%9C%EC%9C%84-%ED%81%90-%EC%82%AC%EC%9A%A9%ED%95%98%EA%B8%B0
