[Java] 우선순위 큐(Priority Queue) 와 객체 정렬

 

우선순위 큐(PriorityQueue) 정리 3줄 요약

용도 : 객체 정렬을 하기 위해(with Comparator, Comparable or 람다식)
특징 1 : 정렬 조건이 여러 개일 경우 유용
특징 2 : 오름차순과 내림차순 가능

 

 

1.  Wrapper class에 우선순위 큐(PriortyQueue) 적용

1-1. 기본형(오름차순)

• PriorityQueue<Integer> pq = new PriorityQueue<>() 으로 선언, element에는 Integer뿐만 아니라 객체 사용가능
• 비교를 위해 Queue도 같이 선언했는데, 코드 아래 출력결과를 보면 큐는 입력받은데로 출력되고, 우선순위 큐는 오름차순으로 출력되는 걸 확인할 수 있음.

public class 우선순위큐 {
    public static void main(String[] args) {
        // 우선순위 큐 선언 방법
        // 1. 기본형 : 오름차순
        PriorityQueue<Integer> pq1 = new PriorityQueue<>();
 
        // pq에 1, 6, 2 입력 => 큐 자료구조는 선입선출임으로 1, 6, 2 순서대로 출력됨
        int[] arr = new int[]{1, 6, 2, 5};
        for (int i : arr) {
            q.offer(i);
            pq1.offer(i);
            pq2.offer(i);
        }
        
        // 비교를 위해 큐 선언 및 출력
        Queue<Integer> q = new LinkedList<>();
        
        System.out.println("=== 큐 출력 ===");
        while (!q.isEmpty()) {
            System.out.print(q.poll() + " ");
        }

        System.out.println();
        
        // 우선순위 큐 출력
        System.out.println("=== 우선순위 큐 오름 차순 출력 ===");
        while (!pq1.isEmpty()) {
            System.out.print(pq1.poll() + " ");
        }
        System.out.println();


    }
}

 

1-2. 오름차순 출력 결과

 

1-3. 내림차순

• PriorityQueue<Integer> pq = new PriorityQueue<>(Collections.reverseOrder()) 으로 선언
• 코드아래 출력결과와 같이 큐, 우선순위큐와 달리 Collections.reverseOrder()를 적용해 내림차순으로 정렬됨.

public class 우선순위큐 {
    public static void main(String[] args) {
        // 우선순위 큐 선언 방법
        // 1. 기본형 : 오름차순
        PriorityQueue<Integer> pq1 = new PriorityQueue<>();

        // 오름차순 사용해보기
        // pq에 1, 6, 2 입력 => 큐 자료구조는 선입선출임으로 1, 6, 2 순서대로 출력됨
        int[] arr = new int[]{1, 6, 2, 5};
        for (int i : arr) {
            q.offer(i);
            pq1.offer(i);
            pq2.offer(i);
        }

		System.out.println("=== 우선순위 큐 오름 차순 출력 ===");
        while (!pq1.isEmpty()) {
            System.out.print(pq1.poll() + " ");
        }
        System.out.println();

        // 2. 내림차순
        PriorityQueue<Integer> pq2 = new PriorityQueue<>(Collections.reverseOrder());

        System.out.println("=== 우선순위 큐 내림차순 출력 ===");
        while (!pq2.isEmpty()) {
            System.out.print(pq2.poll() + " ");
        }
        System.out.println();
    }
}

 

1-4. 내림차순 출력 결과

 

---

 

 

 

2.  객체에 우선순위 큐(PriortyQueue) 적용

• 우선순위 큐에 객체를 적용하기 위해서는 Comparator or Comparable or 람다식이 필요
• 객체는 record 클래스로 선언
  • 객체는 Student이고 이름, 나이, 점수, 키 속성을 가진다.

2-1. Comparable<Student>를 적용

• Comparable을 implements하여 compareTo 메서드를 @Override해야 함
  • 정렬기준 : 나이 
    • this.age() - o.age() : 오름차순
    • o.age() - this.age() : 내림차순
• 비교를 위해 4개의 인스턴스를 리스트에도 담고, PriorityQueue<>에 담고 출력

record Student(String name, int age, int score, int height) implements Comparable<Student> {
    @Override
    public int compareTo(Student o) {
        return this.age() - o.age();
    }
}
public class 객체우선순위큐 {

    public static void main(String[] args) {

        final Student 윌스미스 = new Student("윌스미스", 40, 100, 185);
        final Student 찰리푸스 = new Student("찰리푸스", 31, 80, 175);
        final Student 빌리 = new Student("빌리", 27, 50, 165);
        final Student 제이슨 = new Student("제이슨", 33, 25, 175);

        List<Student> students = List.of(윌스미스, 찰리푸스, 빌리, 제이슨);
        System.out.println("==== 리스트에 담긴 학생들 ====");
        for (Student student : students) {
            System.out.println(student + " ");
        }
        PriorityQueue<Student> pq1 = new PriorityQueue<>();
        for (Student student : students) {
            pq1.offer(student);
        }
        System.out.println();

        System.out.println("==== 나이 기준 오름차순으로 정렬된 우선순위 큐 ====");
        while (!pq1.isEmpty()) {
            System.out.println(pq1.poll() + " ");
        }
        System.out.println();
    }
}

 

2-2. Comparable<Student> 출력 결과

• 입력받은 순서대로 출력된 리스트와 달리 우선순위 큐는 age가 오름차순으로 출력됨

 

 

2-3. Comparator<>를 이용해 점수 기준 오름차순 정렬

• Comparator<Student> scoreComparator = new Comparator<>로 선언
• Comparator는 객체 외부에서 선언해야 함
• Comparable과 유사하게 compare() 메서드를 @Override 함
  • 정렬 기준 : 점수
    • o1.score() - o2.score() : 오름차순
    • o2.score() - o1.score() : 내림차순
• 생성한 scoreComparator를 new PriorityQueue<>(scoreComparator)에 넣어 적용

record Student(String name, int age, int score, int height) implements Comparable<Student> {
    @Override
    public int compareTo(Student o) {
        return this.age() - o.age();
    }
}
public class 객체우선순위큐 {

    public static void main(String[] args) {

        final Student 윌스미스 = new Student("윌스미스", 40, 100, 185);
        final Student 찰리푸스 = new Student("찰리푸스", 31, 80, 175);
        final Student 빌리 = new Student("빌리", 27, 50, 165);
        final Student 제이슨 = new Student("제이슨", 33, 25, 175);

        List<Student> students = List.of(윌스미스, 찰리푸스, 빌리, 제이슨);
        System.out.println("==== 리스트에 담긴 학생들 ====");
        for (Student student : students) {
            System.out.println(student + " ");
        }

        Comparator<Student> scoreComparator = new Comparator<>() {
            @Override
            public int compare(Student o1, Student o2) {
                return o1.score() - o2.score();
            }
        };

        PriorityQueue<Student> pq2 = new PriorityQueue<>(scoreComparator);
        for (Student student : students) {
            pq2.offer(student);
        }

        System.out.println("==== 점수 기준 오름차순 우선순위 큐 ====");
        while (!pq2.isEmpty()) {
            System.out.println(pq2.poll() + " ");
        }


    }
}

 

 

2-4. Comparator<Student> 출력 결과

 

 

2-5. 람다로 객체 정렬

• new PriorityQueue<>(람다식) 선언할 때 바로 람다식을 적용해 정렬
• 정렬기준 :
  • 1순위 : height
    • m1.height() - m2.height() : 오름차순
    • m2.height() - m1.height() : 내림차순
  • 2순위: age
    • m1.age() - m2.age() : 오름차순
    • m2.age() - m1.age() : 내림차순

record Student(String name, int age, int score, int height) implements Comparable<Student> {
    @Override
    public int compareTo(Student o) {
        return this.age() - o.age();
    }
}
public class 객체우선순위큐 {

    public static void main(String[] args) {

        final Student 윌스미스 = new Student("윌스미스", 40, 100, 185);
        final Student 찰리푸스 = new Student("찰리푸스", 31, 80, 175);
        final Student 빌리 = new Student("빌리", 27, 50, 165);
        final Student 제이슨 = new Student("제이슨", 33, 25, 175);

        PriorityQueue<Student> pq3 = new PriorityQueue<>((m1, m2) -> {
            if (m1.height() == m2.height()) {
                return m1.age() - m2.age();
            } else {
                return m1.height() - m2.height();
            }
        });

        for (Student student : students) {
            pq3.offer(student);
        }
        
        System.out.println();
        System.out.println("==== 1. 키 오름차순 2. 나이 오름차순");
        while (!pq3.isEmpty()) {
            System.out.println(pq3.poll() + " ");
        }

    }
}

 

 

2-6. 람다식 우선순위큐 출력 결과

 

 

 

 

이상 전달 끝!