[Heap] Priority Queue(우선 순위 큐)

1. Priority Queue

• 큐의 구조인 FIFO를 가지면서 데이터가 들어온 순서로 나가는 것이 아닌,
  우선 순위를 먼저 결정해서 그 우선 순위가 높은 데이터가 먼저 나가는 자료구조
• 내부 요소는 힙으로 구성되어 이진트리 구조로 이루어짐
• 시간 복잡도는 O(NlogN)

1.1. 선언, 사용

      

      

      

    
    

      <java />
    
import java.util.PriorityQueue;
import java.util.Collections;

//낮은 숫자 기준인 우선순위 큐, 오름차순
PriorityQueue<Integer> priorityQueueLow = new PriorityQueue<>();

//높은 숫자 기준인 우선순위 큐, 내림차순
PriorityQueue<Integer> priorityQueueHigh = new PriorityQueue<>(Collections.reverseOrder());

//String형 낮은 우선순위 큐
PriorityQueue<String> priorityQueue = new PriorityQueue<>(); 

//String형 높은 우선순위 큐
PriorityQueue<String> priorityQueue = new PriorityQueue<>(Collections.reverseOrder());

• 선언시 import java.util.PirorityQueue;

JAVA API - Priority Queue

• Collections.reverseOrder(): 자바에서 제공하는 정적 메서드
  Comparator 인터페이스의 구현체를 반환하며 요소의 순서를 반대로 정렬하는 역할
• PriorityQueue 클래스의 생성자에 Collections.reverseOrder()를 전달하면
  요소가 내림차순으로 정렬되어 MaxHeap 구조를 갖는 우선순위 큐가 생성
• 용량 매개변수를 생략하면 기본적으로 용량이 11인 큐 생성하고, 요소를 추가하면 자동적으로 늘어나게 됨

2022.10.26 - [프로그래밍 언어/Java] - [Java] API_ Collection Framework (List, Set, Map)

[Java] API_ Collection Framework (List, Set, Map)

 

1.2. 실습

https://school.programmers.co.kr/learn/courses/30/lessons/42626

프로그래머스

https://school.programmers.co.kr/learn/courses/30/lessons/138477