아래와 같이 임의의 원소를 offer() 했을 때,
public static void main(String[] args) {
PriorityQueue<Integer> pq = new PriorityQueue<>((o1, o2) -> Integer.compare(o1, o2));
pq.offer(70);
pq.offer(50);
pq.offer(80);
pq.offer(90);
pq.offer(60);
pq.offer(10);
pq.offer(20);
System.out.println(pq);
print(pq);
}
static void print(PriorityQueue<Integer> pq) {
while(!pq.isEmpty()) {
System.out.print(pq.poll() + " ");
}
}
System.out.println, 그리고 poll() 했을 때 위와 같이 다른 결과가 나온다. 단순하게 나는 큐를 한 번에 출력하니까 원소를 임의의 순서로 랜덤으로 출력하는게 아닐까라는 생각이었다. 멍청한건 나였고, 컴퓨터가 귀찮아서 저렇게 랜덤(?)으로 출력한게 아니다.
우선순위 큐는 힙(Heap)구조
힙(heap)은 최댓값 및 최솟값을 찾아내는 연산을 빠르게 하기 위해 고안된 완전이진트리를 기본으로 한 자료 구조라고 한다.
따라서, 위의 출력 값 [10, 60, 20, 90, 70, 80, 50]은 아래의 트리 순서에 따른 것이었다!
힙은 루트 노드에 우선순위가 높은 데이터를 위치시키는 자료구조이다. 힙에 저장된 노드를 뺄 때마다 우선순위가 높은 데이터가 먼저 나온다.
최소 힙(Min Heap)은 완전 이진트리이면서, 루트 노드로 올라갈수록 값이 감소하는 구조다. 최대 힙이던 최소 힙이든 루트 노드에는 우선순위가 높은 것이 위치한다.
새로운 원소가 삽입(offer)된다면 어떻게 될까?
30을 넣어보자.
새 노드를 우선순위가 가장 낮다는 가정을 하고 완전 이진트리를 만족해야 하므로 맨 끝 위치에 저장한다.
부모노드 90이랑 비교해서 값이 더 작으므로 자식노드 30과 노드 위치 교체.
부모노드 60이랑 비교해서 값이 더 작으므로 자식노드 30과 노드 위치 교체.
부모노드 10이랑 비교해서 자식노드 값(30)이 더 크므로 노드 위치 교체하지 않음.
새로운 노드가 삽입되면서 이 과정이 계속 반복된게 바로 [10, 60, 20, 90, 70, 80, 50]의 실체였다.
삭제(poll)는?
우선순위 큐에서의 poll()은 루트 노드를 삭제한다는 의미다. 루트 노드를 지우고 우선순위가 가장 낮은 맨 아래 노드(90)를 루트 노드에 위치시킨다. 그리고 우선순위를 하나씩 비교하면서 최소 힙구조를 유지할 때 까지 반복 비교를 한다.
시행착오를 겪게된 계기
출처: https://school.programmers.co.kr/learn/courses/30/lessons/42885
프로그래머스 구명보트 문제를 풀었는데, 내 생각대로라면 정렬되지 않은 배열 [70, 50, 80, 50] 배열이 우선순위 큐에 들어가면 [50, 50, 70, 80]으로 최소 힙 정렬이 되고, 정렬된 상태로 deque에 넣고 앞 뒤로 빼면 되겠다고 생각을 했지만, 내 생각대로 되지 않았다. 우선순위가 가장 높은 가장 작은 최솟값은 빠질 순 있다. 하지만 가장 큰 값은 빼낼 수가 없다. 왜냐하면 최소/최대 힙은 루트노드를 기준으로 이진트리가 만들어지지 그 외의 노드들까지 오름차순으로 정렬을 하지 않기 때문이다.
그럼 어떻게 할까?
결국, 문제는 배열의 인덱스 순서와 트리 구조의 탐색 순서가 달라서 발생하는 문제다. 두 개의 순서를 일치 시켜버리면 된다. 배열을 먼저 최소힙 형식에 맞게 오름차순 Arrays.sort(arr) 시킨 상태에서 PriorityQueue에 삽입해주면 된다.(List<>형태로 converting 해주어야 함.)
이렇게 하면 System.out.println, 그리고 poll() 했을 때 같은 결과가 나온다.
public static void main(String[] args) {
int[] arr = {70, 50, 80, 90, 60, 10, 20};
Arrays.sort(arr);
PriorityQueue<Integer> pq = new PriorityQueue<>(
Arrays.stream(arr).boxed().collect(Collectors.toList())
);
System.out.println(pq);
print(pq);
}
static void print(PriorityQueue<Integer> pq) {
while(!pq.isEmpty()) {
System.out.print(pq.poll() + " ");
}
}
해결 ✌️
게시글 작성하다가 떠오른 생각인데 위에 문제는 굳이 우선순위 큐에 넣고 다시 데큐에 넣어줄 필요없이 배열 오름차순 정렬 후 바로 데큐에 넣어줘도 된다. (오름차순 정렬을 해야겠다로 우선순위큐를 사용하면서 발생한 문제로 작성한 고찰글이니...)
