Priority Queue, Heap

Priority Queue란?

큐와 유사하지만, 큐의 FIFO와 다르게 우선순위가 높은 값이 먼저 처리되는 트리를 의미한다

특징
1.쉽게 늘어난다.
2.가중치가 낮은 순으로 poll(),peek()가능
3.데이터를 정렬 한 후 출력 가능

❗우선순위 큐는 힙(Heap)으로 구현 가능❗

Heap이란?

힙은 완전 이진 트리이며, 모든 노드의 데이터들은 자식 노드들의 것보다 우선순위가 크거나 같다.

가장 높은 값이 루트에 있는 최대 힙(max heap)과 가장 낮은 값이 루트에 존재하는 최소 힙(min heap)이 있다.

Heap의 데이터 처리 과정

데이터 저장

📝최대힙(Max Heap)

1.가장 마지막 노드에 데이터 삽입
2.부모 노드와 비교하며 삽입된 노드의 데이터가 부모 노드보다 큰 값이라면, 자리 바꿈.
3.바꿀 자리가 존재하지 않을때까지 반복

데이터 삭제

📝최소힙(Min Heap)

1.루트 노드 반환(가장 작은 값)
2.마지막 노드를 루트 노드로 끌어 올림
3.자식 노드와 비교해가며 우선순위가 높은 노드와 자리 바꿈
4.바꿀 자리가 존재하지 않을때까지 반복

우선순위 큐 선언 및 메서드

//최소힙
PriorityQueue<Integer> pq = new PriorityQueue<>();
//최대힙
PriorityQueue<Integer> pq = new PriorityQueue<>(Collections.reverseOrder());

//값 삽입, add는 큐에 공간이 없을 시 exception 발생
pq.add(value);
pq.offer(value);

//첫번째 값 반환 제거 비어있다면 null
pq.poll();
//첫번째 값 제거
pq.remove(); 
//첫번째 값 반환
pq.peek();

//큐 초기화
pq.clear();