우선순위 큐
•
큐는 먼저 들어오는 데이터가 먼저 나가는 FIFO 형식의 자료구조이다.
•
우선순위 큐는 들어오는 순서에 상관없이 우선 순위가 높은 데이터가 먼저 나가는 자료구조이다.
•
우선순위 큐는 힙을 이용하여 구현하는 것이 가장 효율적이다.
Heap
•
여러값들 중에서 가장 큰 값이나 가장 작은 값을 빠르게 찾아내도록 만들어진 자료구조이다.
•
힙은 부모 노드의 키 값이 자식 노드의 키 값보다 항상 작거나 큰 트리를 말한다.
•
완전 이진트리 형태의 자료구조이다.
이진트리
•
이진 트리에서는 중복값을 허용하지 않는다.
•
완전 이진트리는 마지막 레벨을 제외한 모든 레벨이 채워져 있고, 마지막 레벨의 모든 노드는 가능한 가장 왼쪽에 있다.
•
다양한 예시
동작원리
1. 삽입 연산
•
트리의 말단 노드에 새로운 값을 삽입한다.
•
말단부터 루트까지 트리를 거슬러 올라가면서 Heapify 작업을 수행한다.
◦
Heapify: Heap 의 특성을 만족하도록 각 노드들의 위치를 조정하는 과정이다.
2. 삭제 연산
•
루트 노드를 삭제한다.
•
말단 노드를 빈 자리에 가져온다.
•
루트부터 말단까지 내려가면서 Heapify 작업을 수행한다.
선언과 사용
선언
import java.util.*;
PriorityQueue<Integer> priorityQueue = new PriorityQueue<>();
PriorityQueue<Integer> priorityQueueHighest = new PriorityQueue<>(Collections.reverseOrder());
Java
복사
•
default 는 최솟값이 나오게 하는것이다.
•
Collections.reverseOrder 를 사용하면 최댓값이 나오게 된다.
사용
priorityQueue.add();
priorityQueue.poll();
priorityQueue.remove();
priorityQueue.peek();
priorityQueue.element();
priorityQueue.clear();
Java
복사