참고 포스팅

• 우선순위 큐 블로그
• 코딩 팩토리
• 자료구조 이진트리

Priority Queue

우선순위 큐로써 FIFO 구조로 데이터를 in/out 하게 됩니다.

데이터가 들어오면 순서대로 데이터가 나가지 않고 우선순위를 결정하여 우선순위가 높은데이터가 먼저 나가도록 하는 자료 구조입니다.

정수의 경우 작은 숫자가 우선순위가 더 크기 때문에 작은 수부터 우선순위 큐에서 나가도록 Default 되어 있습니다.

우선순위 큐에서 정의한 클래스의 객체를 담기 위해서는 Comparable 인터페이스를 구현(compareTo()) 해줘야 합니다.

Priority Queue는 내부적으로 Heap을 이용하여 구현되어 있습니다.

힙은 완전 이진 트리의 형태를 가지며, $최대 힙$과 $최소 힙$으로 나뉩니다.

💡 완전 이진 트리

다음의 두가지 조건을 충족 해야 합니다.
첫째, 마지막 레벨(level)을 제외하고 모든 노드가 채워져 있어야 합니다.

둘째, 노드는 왼쪽에서 오른쪽 방향으로 채워져야 합니다. 따라서, 어느 노드에 오른쪽 자식이 존재하면, 왼쪽 자식도 가지고 있어야 완전 이진 트리로 볼 수 있습니다.

아래의 그림은 완전 이진 트리를 성립하지 않는 트리입니다.

최대 힙은 부모 노드의 값이 자식보다 크거나 같은 완전 이진 트리를 말합니다. 따라서 트리 내 최대값은 루트 노드입니다.

최소 힙은 부모 노드의 값이 자식보다 작거나 같은 완전 이진 트리를 말합니다. 따라서 트리 내 최솟값은 루트 노드입니다.

Priority Queue 특징

1. 높은 우선순위의 요소를 먼저 꺼내서 처리하는 구조.

2. 내부 요소는 힙으로 구성되어 이진트리 구조.

3. 힙으로 구성되어 있기에 시간 복잡도는 O(NlogN)

4. 우선순위를 중용시 해야하는 경우, 사용하면 유용하게 사용 가능한 자료구조.

Priority Queue 동작

✅ 최소 힙

최소 힙의 경우 루트 노드가 가장 작은 값을 가지고 있다고 했습니다.

최소힙의 경우, 오름차순을 의미하며 값을 빼낼 때, 루트 노드의 최솟값이 빠져 나오게 됩니다.

다음과 같이 값을 우선순위 큐에 담게되면 이진트리가 어떻게 변화하는지에 대해 설명드리겠습니다.

새로운 값을 추가할 때, 오른쪽 맨아래부터 추가를 해주며, 해당 노드가 부모 노드보다 작은지 판단 후 작으면 최소 힙에 의거하여 부모 노드와 교환이 발생하게 됩니다.

반대로 값을 뺄 때는 어떻게 변하는지에 대해 설명드리겠습니다.

위처럼 가장 오른쪽 하부의 노드와 루트 노드를 변경합니다.

그 다음으로 부모 노드를 빼낸 뒤, 다시한번 정렬과정을 거치게 됩니다.

정렬 시, 부모 노드와 자식 노드를 비교하여 자식 노드가 크면 부모와 swap을 하게 됩니다.