230522 Today I Learned

오늘 TIL에는 코테를 풀다가 개념만 얼추 알고있던 우선순위큐로 풀면 되겠다 싶어서 구현 방법을 정리하려한다.

---

우선순위 큐 (Priority Queue)

Java17 공식문서

Queue는 FIFO로 데이터가 나가지만, 우선순위 큐는 데이터의 우선순위를 정해 우선순위가 높은 순서대로 나가게할 수 있다.
힙(Heap)으로 구현 가능하다.

• 기본적으로 최소값(Min) 기준으로 우선순위가 정렬된다.
  최대값(Max)기준으로 하려면 Comparator.reverseOrder()를 써야한다.

• import java.util.PriorityQueue;

• 메서드

Type	Method	Description
boolean	add(E e)	삽입. 큐 용량 부족시 예외 발생
boolean	offer(E e)	삽입. 큐 용량 부족시 false 반환
void	clear()	전체 요소 삭제
boolean	contains(Object o)	요소 포함하고 있는지 확인
E	peek()	최우선순위값 반환만 함. 삭제 x
E	poll()	최우선순위값 반환하면서 삭제
boolean	remove(Object o)	특정 요소 삭제.
int	size()	요소 갯수(크기) 반환
Object[]	toArray()	전체 값들 배열로 반환

• 구현 방법

// min 기준으로 우선순위큐 생성
PriorityQueue<Integer> pqMin = new PriorityQueue<>();
// max 기준으로 우선순위큐 생성. import java.util.Comparator; 임포트 해야한다.
PriorityQueue<Integer> pqMax = new PriorityQueue<>(Comparator.reverseOrder());


// int 배열을 우선순위큐로 바꾸기
int[] a = {5,6,1,2,8}
PriorityQueue<Integer> pq = IntStream.of(a)
	.boxed()	// int -> Integer
    // .collect(Collectors.toCollection(PriorityQueue::new))
    // 최소힙으로 우선순위큐 구현. min 값 기준으로 우선순위
    .collect(Collectors.toCollection(() -> new PriorityQueue<Integer>(Comparator.reverseOrder())));
    // 최대힙으로 우선순위큐 구현. max 값 기준으로 우선순위

pq.peek() // 최대값 8이 반환.
pq.poll() // 최대값 8이 반환되면서 삭제됨
pq.offer(3) // 3을 삽입.
pq.poll() // 최대값 6이 반환되면서 삭제됨