반응형
선형 큐에 대한 설명과 힙(보통 우선순위 큐를 구현할 때 사용되는 자료구조)에 대한 설명은 아래 링크에 있다.
우선순위 큐(Priority Queue)
- 우선순위 큐(Priority Queue)는 먼저 들어오는 데이터가 아니라, 우선순위가 높은 데이터가 먼저 나가는 형태의 자료구조이다. ( 일반적인 큐는 선입선출(FIFO)인 선형 자료구조이다. )
- 일반적으로 힙(Heap)을 이용하여 구현한다. (힙으로 구현했을 때, 우선순위 큐의 Enqueue, Dequeue는 최소(or 최대) 힙의 삽입, 삭제와 같다.)
- Dequeue시, 우선순위가 높은 순서대로 나간다. 우선순위가 같은 경우에는 FIFO가 적용된다.
우선순위 큐의 구현
시간복잡도
| enqueue() | dequeue() | |
| 정렬안된 배열(Unsorted Array) | O(1) | O(N) |
| 정렬안된 연결 리스트 (Unsorted LinkedList) |
O(1) | O(N) |
| 정렬된 배열(Sorted Array) | O(N) | O(1) |
| 정렬된 연결 리스트(Sorted LinkedList) | O(N) | O(1) |
| 힙(Heap) | O(logN) | O(logN) |
- 정렬안된 배열 / 연결 리스트 : 넣을 때 아무렇게나 넣어도 되니까 O(1)이고, 뺄 때는 일일이 살펴봐야 하니까 O(N)이다.
- 정렬된 배열 / 연결 리스트 : 넣을때마다 비교, 자리 비켜주기 등을 해야하기에 O(N)이 걸리고, 뺄때는 앞에꺼 빼기만 하면 되니까 O(1)이다.
- 힙 : enqueue, dequeue 모두 O(logN)의 시간복잡도를 가지기에 보통 우선순위 큐는 힙으로 구현한다.
우선순위 큐(java)
자바에서는 우선순위 큐를 위해 PirorityQueue라는 클래스를 제공해준다.
PriorityQueue<타입> pq = new PriorityQueue(); 이런식으로 사용한다.
타입이 Integer라면 기본적으로 낮은 숫자 순으로 정렬된다.(오름차순) 내림차순으로 정렬하고 싶다면
PriorityQueue<Integer> pq = new PriorityQueue<>(Collections.reverseOrder(); 처럼 하면 된다.
** 타입으로 사용자 지정 클래스를 넣고 싶다면 어떤걸 기준으로 우선순위를 결정할지 클래스에 Comparable<Type> 인터페이스를 implements하고 compareTo 함수를 오버라이딩 해주거나, 람다식으로 우선순위를 어떻게 결정할지 정해주면 된다.
** 데이터 추가(enqueue)에는 add(null 예외처리 필요), offer
데이터 삭제(dequeue)에는 remove(null 예외처리 필요), poll을 쓰면 된다.
예시 코드(java)
class User implements Comparable<User> { // Comparable<타입> 인터페이스 상속
String name;
int age;
public User(String name, int age) {
this.name = name;
this.age = age;
}
// 필수 오버라이드
@Override
public int compareTo(User o) { // 나이 기준으로 정렬해보기
// 1: 변경 안함
// -1: 변경
// 새롭게 추가하는 데이터가 더 작을 때 변경 (작은 값이 위로 올라감, 오름 차순)
return this.age >= o.age ? 1 : -1;
// 새롭게 추가하는 데이터가 더 클 때 변경 (큰 값이 위로 올라감, 내림 차순)
// return this.age >= o.age ? -1 : 1;
}
}
public class Test {
public static void solution(String[] name, int[] age) {
PriorityQueue<User> pq = new PriorityQueue();
for (int i = 0; i < name.length; i++) {
pq.offer(new User(name[i], age[i]));
}
System.out.println("== 내부 힙 구조 ==");
pq.stream().forEach(x -> System.out.println(x.name + " " + x.age));
System.out.println();
System.out.println("== 실제 출력 순서 ==");
while (!pq.isEmpty()) {
User p = pq.poll();
System.out.println(p.name + " " + p.age);
}
}
public static void main(String[] args) {
String[] name = {"A", "B", "C", "D", "E"};
int[] age = {30, 20, 45, 62, 35};
solution(name, age);
// 다른 방식(람다식)
System.out.println();
// 문자열 이름 사전순으로 정렬해보기
PriorityQueue<User> pq = new PriorityQueue<>((User p1, User p2) -> p1.name.compareTo(p2.name));
for (int i = 0; i < name.length; i++) {
pq2.offer(new User(name[i], age[i]));
}
while (!pq2.isEmpty()) {
User p = pq2.poll();
System.out.println(p.name + " " + p.age);
}
}
}반응형
