본문 바로가기
Java

PriorityQueue란?

by asdft 2024. 2. 21.

 

자바 PriorityQueue(우선순위 큐)는 자바의 Queue 인터페이스의 구현 클래스입니다. 일반적인 Queue(큐)의 FIFO(First-In-First-Out)를 따르지만 우선 순위에 따라 요소를 정렬하여 우선 순위가 가장 높은 요소 먼저 처리되도록 합니다.


자바 PriorityQueue는 보통 Heap을 이용하여 구현합니다.
데이터를 삽입할 때 우선순위를 기준으로 Max Heap(최대 힙) 혹은 Min Heap(최소 힙)을 구성하고 데이터를 꺼내거나 삭제할 때는 적절한 자리를 찾아 옮기는 방식으로 진행됩니다.

  • Max Heap(최대 힙) : 최대 값이 우선순위인 큐
  • Min Heap(최소 힙) : 최소 값이 우선순위인 큐

 

특징

  • 높은 우선순위의 데이터를 먼저 꺼내서 처리합니다.
  • 배열과 달리 크기가 고정되어 있지 않습니다.
  • 내부 요소는 Heap(힙)으로 구성되어 이진트리 구조로 이루어져 있다.
  • 요소의 삽입, 삭제의 시간 복잡도는 O(log n)입니다.(n은 대기열의 요소 수)
  • PriorityQueue에 저장할 객체는 필수적으로 Comparable 인터페이스를 구현해야합니다.

 

// Integer 타입으로 우선순위 큐 선언(낮은 숫자 순으로 우선순위 결정)
PriorityQueue<Integer> priorityQueue1 = new PriorityQueue<>();

// Integer 타입으로 우선순위 큐 선언(높은 숫자 순으로 우선순위 결정)
PriorityQueue<Integer> priorityQueue2 = new PriorityQueue<>(Collections.reverseOrder());		
		
// Integer 타입으로 우선순위 큐 선언(낮은 숫자 순으로 우선순위 결정)
PriorityQueue<String> priorityQueue3 = new PriorityQueue<>();

// Integer 타입으로 우선순위 큐 선언(높은 숫자 순으로 우선순위 결정)
PriorityQueue<String> priorityQueue4 = new PriorityQueue<>(Collections.reverseOrder());
PriorityQueue<타입> 변수명 = new PriorityQueue<>(); 

 

 

 

 

 

 

 

출처: https://crazykim2.tistory.com/575 [차근차근 개발일기+일상:티스토리]

'Java' 카테고리의 다른 글

박싱(Boxing) & 언박싱(UnBoxing)  (0) 2024.02.22
[Java 8] Stream의 collect()  (0) 2024.02.22
HashSet 사용법(개념,특징,사용법)  (0) 2024.02.20
[Java] ArrayList와 LinkedList의 차이  (0) 2024.02.18
[Java] ArrayList 사용법  (1) 2024.02.18