Java PriorityQueue 우선순위 큐
* 개요
- 값을 집어 넣으면 정렬하여 상위 10개만 보관하는 코드를 만들고 싶었음.
- 결론은 우선순위 큐는 그런 기능은 없음.
정렬은 하지만, 개수 제한하여 보관하는 코드는 따로 구현해야 ... (그냥 리스트 정렬해서...)
- 기타 1 : PriorityDeque 로 구현하기 쉬울듯 하지만, Java util 엔 이런 자료구조는 없음.
- 기타 2 : CircularFifoQueue (apache commons collections)
- 참고 : 큐에 대한 기본 내용
http://movefast.tistory.com/78
* Integer(기본 자료 클래스) 를 대상으로 할때
PriorityQueue<Integer> pq = new PriorityQueue<Integer>(3);
pq.add(3);
pq.add(2);
pq.add(1);
pq.add(4);
while(!pq.isEmpty()) {
Integer i = pq.poll();
System.out.println(i + "");
}
- poll() 에 의해 나올때는 정렬되어 1,2,3,4 순으로 나옴.
- peek() 은 정렬된 상태의 가장 앞만 나옴.. => 1만 계속 반환
참고 : 우선순위 큐 기본 메서드 , 계산복잡도
- Integer 자체가 Comparable 구현한 것이기 때문에 추가 구현 필요 없는것.
* 일반 객체를 대상으로 할 때
객체 A 가 정렬 대상이라고 할때,
1. A implements Comparable 이거나
2. A 를 위한 Comparator 를 별도로 만들어야 함.
- 참고 : 죄수 출소 Comparable 예제
http://asuraiv.blogspot.kr/2015/11/java-priorityqueue.html
- 1. Comparable 구현 예시
대상 클래스 자체에 비교할 수 있도록 메서드 구현
참고 : http://www.gisdeveloper.co.kr/?p=4452
public class MyClass implements Comparable<MyClass> {
...
@Override
public int compareTo(MyClass target) {
// 오름차순 가정할때
// 현재 객체가 target 보다 작은 수 라면 -1
// 큰 수라면 1
// 동일하다면 0을 반환
}
}
- 2. Comparator 구현 예시
PriorityQueue<Integer> pq = new PriorityQueue<Integer>(1000, new Comparator<Integer>() {
public int compare(Integer w1, Integer w2) {
return w1.compareTo(w2);
}
});
- 참고 : 내가 직접 구현한 클래스 아닌 경우(Jar 사용 등..) Comparable 선언이 힘드므로 Comparator 를 외부에 별도 구현하는게 유용
* Iterator
- poll() 과 달리 요소를 지우지 않고, 리스트 처럼 그냥 순회만 할 경우 사용
- 정렬된 순서대로 순회되지 않음.
- 들어간 순서도 아님. [0] 에 poll() 할 요소만 와있는 상태.
Iterator<Integer> iter = pq.iterator();
while(iter.hasNext()) {
Integer i = iter.next();
System.out.println(i + "");
}
* toArray
- 배열을 가져올 수 있음.
- poll() 과 달리 요소를 지우지 않고, 리스트 처럼 그냥 순회만 할 경우 사용
- 정렬된 순서대로 순회되지 않음.
- 들어간 순서도 아님. [0] 에 poll() 할 요소만 와있는 상태.
int cnt =0;
for(Object o : pq.toArray()) {
System.out.println(cnt + " : " + o);
}
* add() 와 offer() 차이
- 없음. 동일함.
* initialCapacity
- 큐 생성당시 내부 배열의 크기 지정.
- 그렇다고 큐가 빈 채로 생성되는 것도 아님.
(예시의 경우 3 으로 지정했다고 3개의 Null 이 들어간 큐로 생성되는게 아님.)
PriorityQueue<Integer> pq = new PriorityQueue<Integer>(3, new Comparator<Integer>() { ....
* 람다식 이용한 생성 (자바 1.8 이후)
PriorityQueue<T> pq = new PriorityQueue<>(initialCapacity, (e1, e2) -> { return e1.compareTo(e2); });