[Java] 우선순위 큐 (PriorityQueue) 개념 , Comparable

우선순위 큐 (Priority Queue)

 

우선 순위 힙을 기반으로 하는 무제한 우선 순위 대기열입니다. 우선순위 대기열의 요소는 사용되는 생성자에 따라 natural ordering에 따라 정렬되거나 대기열 구성시 제공되는 Comparator에 의해 정렬됩니다.

우선 순위 대기열에서는 null 요소를 허용하지 않습니다. natural ordering에 의존하는 우선 순위 큐는 또한 비교할 수 없는 객체의 삽입을 허용하지 않습니다.

 

우선순위 큐 선언

import java.util.PriorityQueue; //import

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

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

 

우선순위 큐 메소드

PriorityQueue<Integer> Q = new PriorityQueue<>();

Q.offer(1); // 삽입
Q.add(1); // 삽입
Q.peek(); // 꺼내보기
Q.remove(1); // 제거하다
Q.poll(); // 꺼내기

 

Comparable을 이용한 우선순위 큐 정렬



우선순위를 결정해야되는 값이 객체일 경우 Comparable을 이용해 우선순위를 원하는 방식으로 우선순위를 결정 짓게 할 수 있습니다.

학생을 예를들면, 5명의 학생 중 키가 큰순으로 나열해주세요. 만약 키가 같을 경우에는 몸무게가 많이나가는 순으로 정렬해주세요.

 

학생 클래스 생성

class Student implements Comparable<Student>{
    int cm;
    int kg;

    Student(int cm, int kg){
        this.cm = cm;
        this.kg = kg;
    }

    @Override
    public int compareTo ( Student o ) {
        if(o.cm == this.cm) return o.kg - this.kg;
        else return o.cm - this.cm;
    }
}

학생 클래스를 생성후 Comparable의 compareTo() 오버라이딩하여서 구현하였습니다.

compareTo()에서는 대상 학생과 비교 학생의 키를 확인하여 키가 같을 경우에는 몸무게가 큰 순, 키가 같지 않을 경우에는 키순으로 정렬되게 구현하였습니다.

 

우선순위 큐 학생 추가

PriorityQueue<Student> studentPriorityQueue = new PriorityQueue<>();

studentPriorityQueue.offer( new Student( 172,60 ) );
studentPriorityQueue.offer( new Student( 172,65 ) );
studentPriorityQueue.offer( new Student( 178,78 ) );
studentPriorityQueue.offer( new Student( 180,76 ) );
studentPriorityQueue.offer( new Student( 177,75 ) );

 

5명의 학생 데이터를 우선순위 큐에 추가하였습니다.

 

결과

180 76
178 78
177 75
172 65
172 60

키가 큰 순으로 우선순위를 결정짓되 키가 같은 172 학생들은 몸무게가 큰 순으로 우선순위를 결정짓게 하였습니다.