정의

일반적인 큐는 FIFO구조로 이루어져있다. 하지만 우선순위 큐는 FIFO 구조가 아닌 큐 안에서 우선순위를 정하고, 우선순위가 높은 순으로 나가는 구조이다.

일반적으로 힙(Heap) 을 이용해 구현한다. 그러면 힙이란 무엇일까?

힙(Heap)은 우선순위 큐를 위해 고안된 완전이진트리 형태의 자료구조이다.

힙의 특징

• 완전이진트리 형태로 이루어져 있다.
• 부모노드와 서브트리간 대소 관계가 성립된다.
• 이진탐색트리(BST)와 달리 중복된 값이 허용된다.

힙의 종류

최대 힙 (Max Heap)
부모 노드의 키 값이 자식 노드보다 크거나 같은 완전이진트리이다.

최소 힙 (Min Heap)
부모 노드의 키 값이 자식 노드보다 작거나 같은 완전이진트리이다.

---

사용법

선언

import java.util.PriorityQueue;

// 오름차순
PriorityQueue<Type> priorityQueue = new PriorityQueue<>();

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

삽입

// 값 추가
priorityQueue.add(1);
priorityQueue.offer(2);

삭제

// 값 삭제
// priorityQueue의 첫번째 값을 반환하고 제거 비어있다면 null
priorityQueue.poll(); 

// priorityQueue의 첫번째 값 제거
priorityQueue.remove();

// priorityQueue에 있는 숫자 2를 제거 (index 2가 아님!)
priorityQueue.remove(2);

// priorityQueue 초기화
priorityQueue.clear();

추출

// 우선순위가 가장 높은 값 반환
priorityQueue.peek();