[JAVA] PriorityQueue

PriorityQueue 

• 우선순위를 먼저 결정하고 우선순위가 높은 데이터가 먼저 나가는 자료구조

---

PriorityQueue 특징

1. 우선순위가 높은 요소를 먼저 꺼내서 처리하는 구조
2. 내부요소는 Heap으로 구성되어있는 이진트리 구조
3. 내부구조가 Heap으로 구성되어있어 추가 / 삭제시 시간복잡도는 O(NLogN)
4. 값을 비교하기 때문에 NULL 허용이 안됨

---

PriorityQueue 우선순위 설정

//오름차순 
PriorityQueue<Integer> priorityQueue = new PriorityQueue<>();
//내림차순
PriorityQueue<Integer> priorityQueue = new PriorityQueue<>(Collections.reverseOrder());

• 우선수위를 정하는 기준은 Java 정렬기준과 동일 (낮은숫자부터 큰숫자까지 오름차순 정렬)
• Collections.reverseOrder()를 사용하면 내림차순으로 정렬이 가능함 (poll 할경우 가장 큰숫자먼저 꺼내짐)
• Comparator클래스나 Comparable 인터페이스를 사용해서 정렬방식을 변경할 수 있음

---

PriorityQueue 삽입 / 삭제 과정

삽입과정 (Offer메소드)

https://www.codetd.com/en/article/12951127

1. 요소 4를 마지막에 삽입을 함 
2. 요소 4는 부모인 9랑 비교해서 4가 더작으면 SWAP이 진행됨
3. 요소 4가 SWAP이후 부모인 5랑 비교하여 더작으면 SWAP이 또 다시한번 진행됨 
4. 해당 과정을 통해 offer 메소드 동작시 삽입이 되고 정렬이 이루어짐

삭제과정 (Poll메소드)

https://www.codetd.com/en/article/12951127

1. 요소 3을 삭제 진행 
2. 마지막 노드인 요소 9를 루트노드로 SWAP
3. 자식노드인 4와 비교 후 4가 더 작으면 SWAP (ROOT 노드는 4가됨)
4. 요소 9는 SWAP 이후 자식노드인 5와 비교후 4가 더 작으면 SWAP을 함
5. 해당 과정을 통해 poll 메소드 동작시 삭제 되고 정렬이 이루어짐

---

PriorityQueue 예시

PriorityQueue<Integer> priorityQueue = new PriorityQueue<>(Collections.reverseOrder());
priorityQueue.add(1);
priorityQueue.add(4);
priorityQueue.add(3);
//결과 4가 출력
System.out.println(priorityQueue.poll());

• 오름차순 정렬로 선언
• poll로 데이터를 삭제해서 꺼낼경우 결과가 4가 출력이 됨