[자료구조 예제] 우선순위큐 (PriorityQueue)

1) 우선순위큐의 구조는 힙

// 우선순위큐는 기본적으로 최소힙 구조
PriorityQueue<Integer> pq = new PriorityQueue<>();
pq.add(5);
pq.add(2);
pq.add(4);
pq.add(8);
pq.add(6);
System.out.println(Arrays.toString(pq.toArray())); // [2, 5, 4, 8, 6]
// 배열 형태로 출력하기 때문에 levelOrder로 출력
System.out.println(pq.poll()); // 2
System.out.println(pq.poll()); // 4
System.out.println(pq.poll()); // 5
System.out.println(pq.poll()); // 6
System.out.println(pq.poll()); // 8
System.out.println(Arrays.toString(pq.toArray())); // []

// 우선순위큐에서 최대힙구조를 갖도록 매개변수 설정
PriorityQueue<Integer> pq2 = new PriorityQueue<>(Comparator.reverseOrder());
pq2.add(5);
pq2.add(2);
pq2.add(4);
pq2.add(8);
pq2.add(6);
System.out.println(Arrays.toString(pq2.toArray())); // [8, 6, 4, 2, 5]
System.out.println(pq2.poll()); // 8
System.out.println(pq2.poll()); // 6
System.out.println(pq2.poll()); // 5
System.out.println(pq2.poll()); // 4
System.out.println(pq2.poll()); // 2
System.out.println(Arrays.toString(pq2.toArray())); // []

2. 우선순위큐에서 우선순위를 할당하는 예제

// 힙에서 우선순위를 비교하기 위한 변수를 뽑아내는 인터페이스
class Person implements Comparable<Person> {
    String name;
    int age;

    public Person(String name, int age) {
        this.name = name;
        this.age = age;
    }

    // 인터페이스 메서드 오버라이드 부분
    @Override
    public int compareTo(Person o) {
        // 1 리턴 - 위치변경 안함
        // -1 리턴 - 위치변경 함

        // 새롭게 추가한 데이터(this.age)가
        // 기존 데이터(o.age)보다 더 적을때 1 리턴 -> 오름차순
        return this.age >= o.age ? 1 : -1;

        // 내림차순이라면 리턴 값을 반대로
        //return this.age >= o.age ? -1 : 1;
    }
}

public class test {
    public static void solution(String[] name, int[] age) {
        PriorityQueue<Person> pq = new PriorityQueue<>();

        for (int i = 0; i < name.length; i++) {
            pq.offer(new Person(name[i], age[i]));
        }

        System.out.println("== 실제 출력 순서 ==");
        while(!pq.isEmpty()) {
            Person p = pq.poll();
            System.out.println(p.name + "-" + p.age);
        }

    }

    public static void main(String[] args) {
        String[] name = {"A", "B", "C", "D", "E"};
        int[] age = {30, 20, 45, 62, 35};

        solution(name, age); // B-20 A-30 E-35 C-45 D-62

        // 인터페이스 사용하지 않는 경우
        // 객체를 만들 때 어떤 값을 비교할지 인자로 넣어주어서 사용도 가능
        PriorityQueue<Person> pq    // p1이 크면 1, p2가 크면 -1
        = new PriorityQueue<>((Person p1, Person p2) -> p1.age >= p2.age ? 1 : -1);
        // 우선순위큐에 넣기(힙구조)
        for (int i = 0; i < name.length; i++) {
            pq.offer(new Person(name[i], age[i]));
        }
        // 하나씩 꺼내서 출력
        while(!pq.isEmpty()) {
            Person p = pq.poll();
            System.out.println(p.name + "-" + p.age);
        }

        // 나이순이 아니라 문자열로 정렬을 하는 경우
	    // p1과 p2를 비교했을 때 (아스키 값에 따라) 두 문자의 차이값 리턴
        PriorityQueue<Person> pq = new PriorityQueue<>(
                (Person p1, Person p2) -> p1.name.compareTo(p2.name));

        for (int i = 0; i < name.length; i++) {
            pq.offer(new Person(name[i], age[i]));
        }

        while(!pq.isEmpty()) {
            Person p = pq.poll();
            System.out.println(p.name + "-" + p.age);
        }
    }
}

• [A.compareTo(B) 메서드]

  : A를 B와 비교했을 때

  • 같다: return 0
    
  • A가 작다: return 0보다 작은 값
    
  • B가 작다: return 0보다 큰 값
    참고: https://mine-it-record.tistory.com/133

---

마지막 수정일시: 2022-06-14 18:00