[Java/자료구조] 우선순위 큐(PriorityQueue)

---

📢 우선순위 큐

• 우선 순위가 높은 데이터가 먼저 나옴(!= FIFO)
• (1). 모든 테이터에 우선순위가 있다.
• (2). Dequeue 시, 우선순위가 높은 순으로 나감.
• (3). 우선 순위가 같은 경우는  FIFO(선입선출)한다.

📢 우선 순위 큐의 삽입/삭제

• 최소 힙 및 최대 힙의 삽입과 삭제와 같음

📢 구현 하는 방법

• 배열
• 연결 리스트
• 힙 -> 우선순위 큐 자료형 클래스는 힙으로 구성되어있다.

	enqueue()	dequeue()
정렬된 배열	O(n)	O(1)
정렬된 연결 리스트	O(n)	O(1)
힙	O(logN)	O(logN)

📢 PriorityQueue 사용 방법

// 우선순위: 낮은 숫자 순
PriorityQueue<Integer> pq = new PriorityQueue<>();
pq.add(5);
pq.add(7);
pq.add(3);
pq.add(1);
pq.add(9);
System.out.println(Arrays.toString(pq.toArray()));  //[1, 3, 5, 7, 9]


// 우선순위: 높은 숫자 순
PriorityQueue<Integer> pq2 = new PriorityQueue<>(Collections.reverseOrder());
pq2.add(5);
pq2.add(7);
pq2.add(3);
pq2.add(1);
pq2.add(9);
System.out.println(Arrays.toString(pq2.toArray())); //[9, 7, 3, 1, 5]

📢 PriorityQueue 노트 정리