✔️Priority Queue (우선순위 큐)

Priority Queue는 일반적으로 큐와 유사하게 동작하지만, 큐는 선입선출(First-In-First-Out, FIFO)의 원칙을 따르는 반면, 우선순위 큐는 원소들의 우선순위에 따라 먼저 처리된다. 우선순위 큐는 null을 허용하지 않으며, 원소들은 기본적으로 natural order에 따라 정렬된다.

💡 natural order는 주어진 데이터 유형의 기본 정렬 순서를 나타낸다. 자바에서 natural order를 사용하려면 해당 클래스가 Comparable 인터페이스를 구현해야 한다. Comparable 인터페이스는 하나의 메서드, 즉 compareTo를 정의하며, 이 메서드에서는 다른 객체와의 비교 결과에 따라 현재 객체를 순서대로 나열할 수 있다.
예를 들어, String 클래스는 Comparable 인터페이스를 구현하고 있으며, natural order는 사전순(lexicographical order)으로 정렬된다. 따라서 String 객체 간의 natural order는 문자열의 유니코드 코드 포인트를 기반으로 한다.
compareTo 메서드는 현재 객체가 다른 객체보다 작으면 음수, 같으면 0, 크면 양수를 반환합니다. 이러한 반환 값에 따라 정렬이 이루어진다.

public class Example implements Comparable<Example> {
    private String value;

    public Example(String value) {
        this.value = value;
    }

    @Override
    public int compareTo(Example other) {
        return this.value.compareTo(other.value);
    }

    public static void main(String[] args) {
        Example example1 = new Example("banana");
        Example example2 = new Example("apple");

        // compareTo를 사용하여 natural order에 따라 정렬
        int result = example1.compareTo(example2);
	    // 양수 값이 출력되며, "banana"이 "apple"보다 natural order상 뒤에 있음을 나타냄
        System.out.println(result);  
    }
}

선언

  // 오름차순 정렬
PriorityQueue<Integer> pq1 = new PriorityQueue<>(); 

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

구현

요소 삽입
우선순위 큐(최대 힙)는 다음과 같은 단계로 요소를 삽입한다.

1. 새 요소를 트리의 마지막에 삽입한다.
   
2. 힙생성(heapify)한다.

💡 heapify는 이진트리에서 힙 자료구조를 생성하는 과정으로 Min-Heap 또는 Max-Heap을 생성한다.

💡 최소 힙의 경우, parent node는 항상 new node보다 작도록 알고리즘을 수정한다.

요소 삭제
우선순위 큐(최대 힙)는 다음과 같은 단계로 요소를 삭제한다.

1. 삭제할 요소를 선택한다.

2. 삭제할 요소와 가장 마지막 노드를 바꾼다.

3. 가장 마지막 노드(삭제할 요소)를 삭제한다.

4. 힙생성(heapify)한다.

class MaxHeap {

  ArrayList<Integer> heap;

  public MaxHeap() {
    this.heap = new ArrayList<>();
    this.heap.add(0); // index 기준 1부터 시작하도록 더미 데이터 추가
  }

  public void insert(int data) {
    heap.add(data); 
    int cur = heap.size() - 1; 
    while (cur > 1 && heap.get(cur / 2) < heap.get(cur)) { 
      int parentVal = heap.get(cur / 2);
      heap.set(cur / 2, data);
      heap.set(cur, parentVal);

      cur /= 2; // 한 번 더 위로 올라가서 체크
    }
  }
 

📖 Reference
https://www.programiz.com/dsa/priority-queue