특징
Priority Queue는 선입선출 방식을 가지는 Queue와 달리 사용자가 정의한 우선 순위 조건에 의해 가장 먼저 조회/삭제가 이루어지는 데이터가 정해지는 자료구조입니다. Queue는 Enqueue, Dequeue에 대하여 O(1)의 시간복잡도를 가지지만, Priority Queue는 O(log n) 시간 복잡도를 가집니다.
추가로, Priority Queue는 Array기반의 Heap으로 구현합니다. 일반적으로, 트리의 경우 Linked List 기반으로 사용합니다. 하지만, 새로운 노드를 Heap의 마지막 위치에 추가하는 과정이 필요한데, Array 기반(엄밀히 말하자면 인덱스를 가지고 있는 리스트)의 Heap으로 구현해야 해당 과정이 수월하기 때문입니다.
Heap이란?
특징
Heap은 최대힙, 최소힙으로 나뉩니다. 최대힙이란 부모 노드가 자식 노드보다 큰 상태를 유지해야 하고, 최소힙이란 부모 노드가 자식 노드보다 작은 상태를 유지해야 합니다.
일반적으로 Array 기반으로 구현하나 이해를 돕기 위해 트리 형태로 살펴보도록 하겠습니다.
위 그림을 통해 최대힙과 최소힙을 살펴보면 앞에서 말한 상태를 유지하는 것을 확인할 수 있습니다. 즉, 루트 노드가 가장 큰 수(최대힙) 또는 가장 작은 수(최소힙)를 가지고 있는 상태가 유지됩니다.
추가, 삭제 과정
Heap의 추가, 삭제 과정을 그림을 통해 살펴보도록 하겠습니다.
추가 (Push)
1. 마지막 위치에 추가
2. 부모 노드와 비교하며 우선 순위 결정
삭제 (Pop)
1. 루트 노드 데이터를 기억한 후 삭제
2. 마지막 위치에 있는 노드를 루트 노드로 설정
3. 루트 노드에서 부터 우선 순위 결정
위 그림을 보면 추가, 삭제 과정에서 트리 높이(log n) 만큼 비교 과정을 추가 수행하는 것을 볼 수 있습니다. 이로 인해, Heap의 추가/삭제 연산이 O(log n)의 시간 복잡도를 가지는 것을 확인할 수 있었습니다.
또한, Push 연산시 마지막 노드에 추가하는 것 또한 볼 수 있습니다. 이는 Array 기반의 Heap을 사용해야 하는 이유입니다.
예상 질문
Priority Queue는 어떤 자료구조인가요?
선입선출 방식을 가지는 Queue와 달리 사용자가 정의한 우선 순위에 따라 가장 먼저 조회/삭제가 수행되는 데이터가 결정되는 자료구조입니다.
Priority Queue는 어떻게 구현되나요?
Array 기반의 Heap을 사용해 구현합니다. 이는, Enqueue 과정시 마지막 위치에 데이터를 추가해야 하기 때문입니다. 추가로, Heap으로 구현했기 때문에 추가/삭제시 트리 높이인 O(log n)의 시간 복잡도를 가집니다.
