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

❓ PriorityQueue란

FIFO 형식으로 처리되는 큐(Queue)와 달리우선순위가 높은 요소가 먼저 처리되는 자료구조

• 각 요소가 우선순위를 가지고 있음
• 일반적으로 힙(Heap) 구조를 이용해 구현

🧐 힙(Heap)은 뭐야

완전이진트리 형태의 자료구조

• 최소 힙(Min Heap)
  부모 노드의 값이 자식 노드의 값보다 작거나 같음

      10
     /  \
    20   15
   / \   / \
  40 50 30 25

• 최대 힙(Max Heap)
  부모 노드의 값이 자식 노드의 값보다 크거나 같음

      50
     /  \
    30   40
   / \   / \
  10 20 35 25

☕️ in Java

• java.util 패키지에 포함된 클래스 사용
• 힙(Heap) 자료구조를 사용하여 효율적인 삽입, 제거 연산 수행
• 기본 구조는 최소 힙

선언

PriorityQueue<T> pq = new PriorityQueue<>();

삽입 및 삭제

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

// 삽입
pq.add(10);
pq.add(20);
pq.add(15);

// 삭제
pq.poll(); // 10
pq.poll(); // 15
pq.poll(); // 20

🔵 우선순위 지정

최대 힙

• 우선순위 큐는 기본적으로 최소 힙 형태를 가짐
• Comparator 사용해 최대 힙 구현 가능

PriorityQueue<Integer> pq = new PriorityQueue<>(Collections.reverseOrder());

// 삽입
pq.add(10);
pq.add(20);
pq.add(15);

// 삭제
pq.poll(); // 20
pq.poll(); // 15
pq.poll(); // 10

사용자 정의

• Comparator 구현

PriorityQueue<String> pq = new PriorityQueue<>(new Comparator<String>() {
            public int compare(String o1, String o2) {
                return o1.charAt(1) - o2.charAt(1);
            }
        };);

// 삽입
pq.add("apple");
pq.add("banana");
pq.add("cold");
pq.add("error");

// 삭제
pq.poll(); // banana
pq.poll(); // cold
pq.poll(); // apple
pq.poll(); // error