[자료구조] - 우선순위 큐

Priority Queue 우선순위 큐

• 일반적인 큐의 구조(FIFO)를 가지면서, 데이터가 들어온 순서대로 데이터가 나가는 것이 아닌 우선순위를 먼저 결정하고 그 우선순위가 높은 데이터가 먼저 나가는 자료구조
• PriorityQueue를 사용하기 위해선 우선순위 큐에 저장할 객체는 필수적으로 Comparable Interface를 구현해야함
• Comparable Interface를 구현하면 compareTo method를 override 하게 되고 해당 객체에서 처리할 우선순위 조건을 리턴해주면 PriorityQueue가 우선순위가 높은 객체를 추출 해줌.
• Heap을 이용하여 구현하는 것이 일반적임(자바)

특징

• 높은 우선순위의 요소를 먼저 꺼내서 처리하는 구조
  • 우선순위 큐에 들어가는 원소는 비교가 가능한 기준이 있어야한다.
• 내부 요소는 힙으로 구성되어 이진트리 구조로 이루어져 있다.
• 시간 복잡도 O(NLogN)
• 우선순위를 중요시해야 하는 상황에서 주로 사용

요소 추가

 

• add(E e):
  • 큐가 꽉 차면 예외를 던짐
  • 요소가 정상적으로 추가되면 true를 반환
• offer(E e):
  • 큐가 꽉 차면 false를 반환
  • 요소가 정상적으로 추가되면 true를 반환

요소 삭제

 

• poll():
  • 큐의 우선순위가 가장 높은 요소를 제거하고 반환
  • 큐가 비어 있으면 null을 반환
• remove():
  • 특정 요소를 제거
  • 지정된 요소가 큐에 존재하면 그것을 제거하고 true를 반환. 존재하지 않으면 false를 반환
  • 예외를 던지는 것이 아니라 boolean을 반환하기 때문에 안전하게 사용할 수 있음
• clear():
  • 큐의 모든 요소를 제거
• peek():
  • 큐의 우선순위가 가장 높은 요소 를 반환하지만 제거하지 않음
  • 큐가 비어 있으면 null을 반환

기본 사용 (자연 순서, 최소 힙)

기본적으로 PriorityQueue는 요소의 자연 순서를 사용하여 최소 힙을 형성

자연 순서를 사용하는 예제)

import java.util.PriorityQueue;

public class PriorityQueue {
    public static void main(String[] args) {
        // 정수를 저장하는 우선순위 큐 선언 (기본적으로 최소 힙 사용)
        PriorityQueue<Integer> priorityQueue = new PriorityQueue<>();

        // 요소 추가 (enqueue)
        priorityQueue.add(5);
        priorityQueue.add(1);
        priorityQueue.add(3);
        priorityQueue.add(2);
        priorityQueue.add(4);
        
        // 우선순위 큐의 요소 출력
        System.out.println("Priority Queue Elements: " + priorityQueue);

        // 요소 제거 및 출력
        while (!priorityQueue.isEmpty()) {
            int element = priorityQueue.poll();  // poll()은 우선순위가 가장 높은 요소를 제거하고 반환
            System.out.println("Removed Element: " + element);
        }
    }
}

 

사용자 정의 순서 사용 (Comparator)

사용자 정의 Comparator를 사용하여 우선순위를 설정할 수 있음

예를 들어, 최대 힙을 구현하려면 다음과 같이 Comparator를 사용할 수 있다

import java.util.Collections;
import java.util.PriorityQueue;

public class CustomOrderPriorityQueue {
    public static void main(String[] args) {
        PriorityQueue<Integer> maxHeap = new PriorityQueue<>(Collections.reverseOrder());

        // 요소 추가
        maxHeap.add(5);
        maxHeap.add(1);
        maxHeap.add(3);
        maxHeap.add(2);
        maxHeap.add(4);

        // 요소 제거 및 출력 (사용자 정의 순서: 최대 힙)
        while (!maxHeap.isEmpty()) {
            System.out.println(maxHeap.poll());
        }
    }
}

 

 

Comparator를 직접 구현하기

Collections.reverseOrder() 대신 직접 Comparator를 구현하여 사용자 정의 정렬 순서를 지정할 수도 있음

예를 들어, 문자열 길이에 따라 정렬하는 PriorityQueue를 만들 수 있다

import java.util.PriorityQueue;
import java.util.Comparator;

public class CustomComparatorPriorityQueue {
    public static void main(String[] args) {
        // 문자열 길이에 따라 정렬하는 Comparator
        Comparator<String> lengthComparator = new Comparator<String>() {
            @Override
            public int compare(String s1, String s2) {
                return Integer.compare(s1.length(), s2.length());
            }
        };

        PriorityQueue<String> lengthPriorityQueue = new PriorityQueue<>(lengthComparator);
        // 요소 추가
        lengthPriorityQueue.add("apple");
        lengthPriorityQueue.add("banana");
        lengthPriorityQueue.add("cherry");
        lengthPriorityQueue.add("date");

        // 요소 제거 및 출력 (문자열 길이 순서)
        while (!lengthPriorityQueue.isEmpty()) {
            System.out.println(lengthPriorityQueue.poll());
        }
    }
}