오늘은 자바 PriorityQueue(우선 순위 큐)에 대해서 알아보겠습니다. 자바 PriorityQueue는 Queue(큐)의 FIFO(First-In-First-Out)를 따르지만 요소를 정렬하여 우선 순위가 가장 높은 요소 먼저 처리되도록 합니다. 그럼 바로 자바 PriorityQueue의 특징과 사용법, 정렬, 시간 복잡도에 대해서 알아보겠습니다.
목차
자바 PriorityQueue란???
자바 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 인터페이스를 구현해야합니다.
자바 PriorityQueue 사용법
선언
1 2 3 4 5 6 7 8 | import java.util.PriorityQueue; import java.util.Collections; //낮은 숫자가 우선 순위(오름차순)인 int 형 우선순위 큐 선언 PriorityQueue<Integer> priorityQueueLowest = new PriorityQueue<>(); //높은 숫자가 우선 순위(내림차순)인 int 형 우선순위 큐 선언 PriorityQueue<Integer> priorityQueueHighest = new PriorityQueue<>(Collections.reverseOrder()); | cs |
우선 순위의 기본값은 오름차순이고 내림차순으로 정렬하려면 Collections.reverseOrder()를 표시해줘야합니다.
데이터 추가
- add(value) : value 데이터 추가, Collection 클래스 메소드
- offer(value) : value 데이터 추가, Queue 클래스 메소드
1 2 3 4 5 6 7 8 9 10 11 12 13 | import java.util.PriorityQueue; import java.util.Collections; //낮은 숫자가 우선 순위인 int 형 우선순위 큐 선언 PriorityQueue<Integer> pq = new PriorityQueue<>(); pq.add(1); pq.add(20); pq.add(8); pq.add(9); pq.add(14); pq.offer(17); pq.add(2); | cs |
<결과>
결과를 보면 데이터를 추가한 순서와 상관없이 우선순위 큐만의 정렬 방식으로 출력됩니다. 우선순위 큐는 삭제나 조회 메소드를 호출했을 때, 루트 노드를 기준으로 실행합니다. 그렇기 때문에 루트 노드 외에는 정렬되지 않습니다.
데이터 추가 과정
1.PriorityQueue에 마지막에 숫자 2를 추가해줍니다.
2.부모의 값과 비교해서 더 작으면 스왑합니다. 2와 8 교환 (2<8)
3.부모의 값이 더 작기 때문에 스왑하지 않습니다. (2 > 1)
데이터 삭제
- poll() : 우선순위가 가장 높은 값을 삭제, 비어있다면 null
- remove() : 우선순위가 가장 높은 값을 삭제, 비어있다면 예외 발생
- clear() : 모든 값을 삭제
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 | import java.util.PriorityQueue; import java.util.Collections; public class Main { public static void main(String[] args) { //낮은 숫자가 우선 순위인 int 형 우선순위 큐 선언 PriorityQueue<Integer> pq = new PriorityQueue<>(); pq.add(1); pq.add(20); pq.add(8); pq.add(9); pq.add(14); pq.offer(17); pq.add(2); System.out.println(pq); pq.poll(); // 우선 순위가 가장 높은 값 삭제 System.out.println(pq); pq.remove(); // 우선순위가 가장 높은 값을 삭제, 비어있다면 예외 발생 System.out.println(pq); pq.clear(); //모든 값을 삭제 System.out.println(pq); } } | cs |
<결과>
데이터 삭제 과정
가장 높은 우선순위의 데이터를 삭제한다는 상황으로 예시를 들어보겠습니다.
1.가장 높은 우선순위인 1을 삭제하는 경우입니다. 루트 노드인 1과 마지막 노드인 8을 스왑합니다.
2. 사이즈를 줄이고 8과 양쪽의 자식 노드와 비교합니다.
3. Min Heap(최소 힙)이라 8보다 작은 2를 부모인 8과 비교합니다.
4. 2가 더 작으므로 스왑합니다.
5. 이제 스왑한 8은 다시 자식 노드와 비교하는 과정을 거칩니다. 이 경우엔 8이 9보다 작으므로 변경사항이 없습니다.
크기 구하기
- size() : 크기를 출력해줍니다.
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 | import java.util.PriorityQueue; import java.util.Collections; public class Main { public static void main(String[] args) { //낮은 숫자가 우선 순위인 int 형 우선순위 큐 선언 PriorityQueue<Integer> pq = new PriorityQueue<>(); pq.add(1); pq.add(20); pq.add(8); pq.add(9); pq.add(14); pq.offer(17); pq.add(2); System.out.println(pq.size()); } } | cs |
결과 : 7
데이터 출력
- peek() : 우선순위가 가장 높은 값 출력, 비어있으면 null을 반환
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 | public class Main { public static void main(String[] args) { //낮은 숫자가 우선 순위인 int 형 우선순위 큐 선언 PriorityQueue<Integer> pq = new PriorityQueue<>(); pq.add(1); pq.add(20); pq.add(8); pq.add(9); pq.add(14); pq.offer(17); pq.add(2); System.out.println(pq); System.out.println(pq.peek()); // 향상된for문을 사용하여 값 출력 for(Integer i : pq) System.out.print(i + ” “); System.out.println(); // Iterator 사용 값 출력 Iterator iter = pq.iterator(); while(iter.hasNext()) System.out.print(iter.next() + ” “); System.out.println(); // forEach()메소드를 통해 출력( 자바 8부터 사용할 수 있다) pq.stream().forEach(System.out::print); } } | cs |
자바 PriorityQueue에서 peek 메서드를 사용하면 우선 순위가 가장 높은 값을 출력할 수 있습니다. 전체 PriorityQueue의 값을 출력하려면 향상된 for문, Iterator, forEach()를 사용하면 됩니다.
결과
자바 PriorityQueue 정렬
자신이 만든 클래스에 PriorityQueue를 사용하려면 Comparable 인터페이스를 implements 하고 compareTo 메서드를 자신이 원하는 우선순위에 맞게 구현해 주면 됩니다.
예시)
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 | class Person implements Comparable<Person> { private String name; private int age; public Person(String name, int age) { this.name = name; this.age = age; } // 나이를 기준으로 compareTo() 오버라이딩 @Override public int compareTo(Person otherPerson) { return Integer.compare(this.age, otherPerson.age); } @Override public String toString() { return name + ” (Age: “ + age + “)”; } } public class Main { public static void main(String[] args) { //낮은 숫자가 우선 순위인 int 형 우선순위 큐 선언 PriorityQueue<Person> pq = new PriorityQueue<>(); // 데이터 추가 pq.add(new Person(“Alice”, 30)); pq.add(new Person(“Bob”, 25)); pq.add(new Person(“Charlie”, 35)); pq.add(new Person(“David”, 28)); // 나이가 어린 순으로 정렬 while (!pq.isEmpty()) { System.out.println(pq.poll()); } } } | cs |
결과
Comparable 인터페이스를 구현한 Person 클래스를 생성하였습니다. Person 클래스는 나이를 기준으로 compareTo()를 오버라이딩했습니다. 결과를 보면 데이터를 추가한 순서 상관없이 정렬된 상태로 출력되었습니다.
자바 PriorityQueue 시간 복잡도
| PriorityQueue | 시간 복잡도 |
|---|---|
| 요소 추가(삽입) | O(log n) |
| 최우선 순위 제거 | O(log n) |
| 최고 우선순위 확인 | O(1) |
| 요소 검색 | O(n) |
| 크기(요소 수) | O(1) |
| 배열/목록으로 변환 | O(n) |
결론
오늘은 자바 PriorityQueue에 대해서 알아봤습니다. 자바 PriorityQueue 자신이 원하는 우선순위를 가지고 정렬할 수 있고 검색 시간이 빠르기 때문에 필요하시다면 사용하시면 좋을 것 같습니다. 자바 PriorityQueue말고도 자바에 대해서 궁금한 내용이 있으시다면 아래 링크를 클릭해주세요.
자바 관련 추가 정보
- LinkedList에 대해서 궁금하시다면 여기를 클릭해 주세요.
- Vector에 대해서 궁금하시다면 여기를 클릭해 주세요.
- List 인터페이스에 대해서 궁금하시다면 여기를 클릭해 주세요.
- Set 인터페이스에 대해서 궁금하시다면 여기를 클릭해 주세요.
- 최신 자바 프레임 워크가 궁금하시다면 여기를 클릭해 주세요.