우선순위 큐(Priority Queue) 란?#
우선순위 큐(Priority Queue)는 일반적인 큐의 구조와 달리 들어가는 순서와 상관없이 정의한대로 우선순위를 먼저 결정하고 그
우선순위가 높은 데이터가 먼저 나가는 자료구조 입니다.
그렇기 때문에 dequeue를 하면 이미 정의한 순서에 맞게 가장 위의 값이 나타납니다.
우선순위 큐는 힙을 기반으로 하는 완전이진트리로 우선순위를 정하게 됩니다.
사용 방법#
우선순위 큐는 우선순위가 꼭 필요한 경우에 사용합니다.
람다식으로 정의해도 되고 Comparable을 이용해서 정의해도 됩니다.
1
2
3
4
5
6
7
8
9
10
11
12
13
| // 낮은 숫자가 우선순위가 높은 방식
PriorityQueue<Integer> pq = new PriorityQueue<>();
// 높은 숫자가 우선순위가 높은 방식
PriorityQueue<Integer> pq = new PriorityQueue<>(Collections.reverseOrder());
// 이중 배열에서 0번째 낮은 숫자가 우선순위가 높은 방식(람다식)
PriorityQueue<int[]> pq = new PriorityQueue<>((o1, o2) -> o1[0] - o2[0]);
// 이중 배열에서 0번째 낮은 숫자가 우선순위가 높은 방식(Comparator)
PriorityQueue<int[]> pq = new PriorityQueue<>(new Comparator<int[]>() {
@Override
public int compare(int[] o1, int[] o2) {
return o1[0] - o2[0];
};
});
|
위 처럼 다양한 방법으로 우선순위를 정할 수 있습니다.
간단한 예제 및 원리#
간단히 예를 들어 가장 작은 수를 기준으로 우선순위 큐를 만들면
1
2
3
4
5
6
7
8
| PriorityQueue<Integer> pq = new PriorityQueue<>();
pq.offer(1);
pq.offer(2);
pq.offer(3);
pq.offer(4);
pq.offer(5);
pq.offer(6);
pq.offer(7);
|
의 형태로 만들어집니다.
그렇지만 각각 enqueue할 때는 이진트리의 마지막부분에서 조건에 맞게 값이 들어가는거죠.
위의 경우는 가장작은 수부터 차례로 들어가기 때문에 swap을 하지 않고 값이 들어가게됩니다.
그렇지만 만약 큰 수부터 우선순위 큐를 하게 되면
1
2
3
4
5
6
7
8
| PriorityQueue<Integer> pq = new PriorityQueue<>(Collections.reverseOrder());
pq.offer(1);
pq.offer(2);
pq.offer(3);
pq.offer(4);
pq.offer(5);
pq.offer(6);
pq.offer(7);
|
의 형태로 만들어집니다.
위의 순서를 그림으로 그리면 아래와 같은 순서로 완전 이진트리 형태로 값이 들어갑니다.
조건에 맞게 우선 가장 마지막 노드에 값이 들어가고 부모와 비교를 해서 자신의 위치를 찾아가는 것이죠.
반대로 dequeue인 poll()의 경우는 우선 Root를 제거하고 가장 마지막의 노드를 Root로 가져온 뒤 자식노드 중 자신보다 우선순위가 높은 값이 있다면 Swap을 하여 자신의 위치를 찾아가는 식입니다.
1
2
3
| while (!pq.isEmpty()) {
pq.poll();
}
|
실제로 코드 내부로 들어가면 enqueue의 경우는 아래와 같이 Comparable로 정의하고 부모 노드와 현재 노드를 변경하는 코드가 들어가 있습니다.
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
39
40
41
42
43
44
| public boolean offer(E e) {
if (e == null)
throw new NullPointerException();
modCount++;
int i = size;
if (i >= queue.length)
grow(i + 1);
siftUp(i, e);
size = i + 1;
return true;
}
private void siftUp(int k, E x) {
if (comparator != null)
siftUpUsingComparator(k, x, queue, comparator);
else
siftUpComparable(k, x, queue);
}
private static <T> void siftUpComparable(int k, T x, Object[] es) {
Comparable<? super T> key = (Comparable<? super T>) x;
while (k > 0) {
int parent = (k - 1) >>> 1;
Object e = es[parent];
if (key.compareTo((T) e) >= 0)
break;
es[k] = e;
k = parent;
}
es[k] = key;
}
private static <T> void siftUpUsingComparator(
int k, T x, Object[] es, Comparator<? super T> cmp) {
while (k > 0) {
int parent = (k - 1) >>> 1;
Object e = es[parent];
if (cmp.compare(x, (T) e) >= 0)
break;
es[k] = e;
k = parent;
}
es[k] = x;
}
|
마찬가지로 dequeue의 경우도 Comparable로 정의하고 child 노드와 현재 노드를 변경하는 식의 코드가 들어있습니다.
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
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
| public E poll() {
final Object[] es;
final E result;
if ((result = (E) ((es = queue)[0])) != null) {
modCount++;
final int n;
final E x = (E) es[(n = --size)];
es[n] = null;
if (n > 0) {
final Comparator<? super E> cmp;
if ((cmp = comparator) == null)
siftDownComparable(0, x, es, n);
else
siftDownUsingComparator(0, x, es, n, cmp);
}
}
return result;
}
private static <T> void siftDownComparable(int k, T x, Object[] es, int n) {
// assert n > 0;
Comparable<? super T> key = (Comparable<? super T>)x;
int half = n >>> 1; // loop while a non-leaf
while (k < half) {
int child = (k << 1) + 1; // assume left child is least
Object c = es[child];
int right = child + 1;
if (right < n &&
((Comparable<? super T>) c).compareTo((T) es[right]) > 0)
c = es[child = right];
if (key.compareTo((T) c) <= 0)
break;
es[k] = c;
k = child;
}
es[k] = key;
}
private static <T> void siftDownUsingComparator(
int k, T x, Object[] es, int n, Comparator<? super T> cmp) {
// assert n > 0;
int half = n >>> 1;
while (k < half) {
int child = (k << 1) + 1;
Object c = es[child];
int right = child + 1;
if (right < n && cmp.compare((T) c, (T) es[right]) > 0)
c = es[child = right];
if (cmp.compare(x, (T) c) <= 0)
break;
es[k] = c;
k = child;
}
es[k] = x;
}
|