[JAVA/자료구조] 우선순위 큐(Priority Queue) (Heap)

우선순위 큐(Priority Queue)

우선순위 큐는 Queue와 비슷하지만, 선입선출 구조인 Queue와 달리 Queue에 들어있는 자료 중 우선순위를 설정하여

우선순위가 높은 순서대로 데이터를 꺼내는 구조이다.

큐에 들어오는 모든 데이터에 우선순위가 존재하며, 데이터를 꺼낼 때 우선순위가 높은 순서대로 나온다.

우선순위가 같은 경우에는 선입선출 방식을 따른다.

자바의 우선순위 큐는 힙(Heap) 방식으로 구현되어 있다.

 

아래 링크에 Heap에 대해 정리해 두었으니 확인하길 바란다.
2023.06.11 - [자료구조] - [JAVA/자료구조] 힙(Heap), 최소 힙(Min Heap), 최대 힙(Max Heap)

---

우선순위 지정

PriorityQueue는 생성할 때 우선순위를 지정해주어야 한다.

자바에서 지원하는 기본 타입들에 대해서는 기본정렬방법(오름차순)을 따른다.

 

그러나 임의의 클래스로 구성된 PriorityQueue 또는 기본 타입의 경우에도 우선순위를 선정하는 방법을 변경하려는 경우에는 우선순위를 따로 지정해 주어야 한다.

이때, 클래스에 Comparable인터페이스를 구현하거나, PriorityQueue 생성시에 Comparator를 매개변수로 넣어주거나, 매개변수에 람다식을 작성하는 방식으로 우선순위를 지정해 줄 수있다.

아래 링크는 Comparator, Comparable에 대해 정리된 글이다.
2023.06.10 - [JAVA/JAVA 클래스] - [JAVA] Comparator / Comparable - 정렬을 위한 클래스(인터페이스)

---

우선순위 큐 생성

1. 기본 생성 

매개변수에 아무 값도 넣지 않으면 기본 정렬 방법(오름차순)을 따른다.

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

만약 아래와 같이 클래스로 구성된 PriorityQueue의 경우에는 poll() 할 때, 해당 클래스에 Comparable이 구현되지 않았다는 예외가 발생한다.

PriorityQueue<MyMember> memberQueue = new PriorityQueue<>();

Exception in thread "main" java.lang.ClassCastException: class MyMember cannot be cast to class java.lang.Comparable

---

2. Comparable 구현

임의의 클래스로 구성된 PriorityQueue의 경우에 해당 클래스에 Comparable Interface를 상속받아서 compareTo 메서드를 구현해주면 우선순위를 지정해줄 수 있다.

class MyMember implements Comparable<MyMember>

class MyMember implements Comparable<MyMember>{
    String name;
    int age;

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

    @Override
    public int compareTo(MyMember o) {
        return this.age-o.age;
    }
}

PriorityQueue<MyMember> memberQueue = new PriorityQueue<>();
memberQueue.offer(new MyMember("memA",20));
memberQueue.offer(new MyMember("memB",10));
memberQueue.offer(new MyMember("memC",30));

이 때, age를 기준으로 compareTo메서드를 구현해주었기 때문에

우선순위는 memB(age=10) >  memA(age=20) >  memC(age=30) 이 된다.

---

3. 람다식 이용

PriorityQueue 생성시에 매개변수로 람다식을 작성하여 우선순위를 지정해 줄 수있다.

PriorityQueue<MyMember> memberQueue = new PriorityQueue<>((m1,m2)->m1.age-m2.age);

---

4. Comparator 이용

원래는 Comparator을 만들어주는 것이 기본이었으나, 자바8부터 람다식이 도입된 이후 람다식으로 간단하게 나타낸 것이다.

PriorityQueue 생성시에 매개변수로 Comparator클래스의 compare메서드를 구현하여 우선순위를 지정해 줄 수있다.

PriorityQueue<MyMember> memberQueue = new PriorityQueue<>(new Comparator<MyMember>() {
    @Override
    public int compare(MyMember o1, MyMember o2) {
        return o1.age - o2.age;
    }
});

---

예제 Code 1

Integer 타입의 PriorityQueue를 생성하고 값을 넣어주면, 최소 힙(Min Heap) 방식으로 우선순위가 지정된다.

그러나 MinHeap 방식의 특성에 따라 형제노드 간에는 크기비교가 보장되지 않아서, queue에서 값을 꺼내지 않은 상태에선 완벽하게 정렬되어있지 않다. [1, 2, 3, 5, 4]

이후 queue의 모든 값을 순차적으로 꺼내올때는 작은 값부터 출력되는 것을 확인할 수 있다.

PriorityQueue<Integer> queue = new PriorityQueue<>();
queue.offer(1);
queue.offer(5);
queue.offer(3);
queue.offer(4);
queue.offer(2);
System.out.println(queue); 
//출력 : [1, 2, 3, 5, 4]

System.out.print("queue.poll() => ");
while (!queue.isEmpty()){
    System.out.print(queue.poll()+" ");
}
//출력 : queue.poll() => 1 2 3 4 5

---

예제 Code 2

이번엔 임의로 만든 클래스에서 나이가 큰 순으로 정렬하는 예제이다.

위에 람다식 생성 부분에서와 반대로 이번엔 람다식을 (o1, o2) -> o2.age-o1.age 로 변경했다.

이제 MyMember 객체의 나이가 큰 순으로 반환되는 것을 확인할 수 있다.

class MyMember{
    String name;
    int age;

    public MyMember(String name, int age) {
        this.name = name;
        this.age = age;
    }
}
public class TEST {
    public static void main(String[] args){
        PriorityQueue<MyMember> memberQueue = new PriorityQueue<>((o1, o2) -> o2.age-o1.age);
        memberQueue.offer(new MyMember("memA",20));
        memberQueue.offer(new MyMember("memB",10));
        memberQueue.offer(new MyMember("memC",30));
        
        System.out.println("=== memberQueue.poll() ===");
        while (!memberQueue.isEmpty()){
            MyMember member = memberQueue.poll();
            System.out.println("age : "+member.age+" | name : "+member.name);
        }
    }
}

(출력)

=== memberQueue.poll() ===
age : 30 | name : memC
age : 20 | name : memA
age : 10 | name : memB