Priority Queue
개념
- 특정 상황에서 저장된 값들의 우선순위가 중요한 경우가 있을 수 있음
- 이러한 우선순위 개념을 적용한 것 Priority Queue라는 자료구조
- 저장된 값들은 특정 우선순위를 가지며, 높은 우선순위를 가진 값이 먼저 제거됨
- 이러한 우선순위를 조절해 Priority Queue를 통해 Stack, Queue 모두 구현할 수 있음
- Array나 Linked List를 통해 구현할 수도 있지만 Heap 구조를 통해서도 구현 가능
구분
- Min-priority Queue: 우선순위가 가장 낮은 요소가 먼저 제거됨
- Max-priority Queue: 우선순위가 가장 높은 요소가 먼저 제거됨
구현
1. Array
- 삽입시 배열의 마지막에 추가하면되므로
O(1)의 시간복잡도가 소요 (장점) - 삭제시, 가장 우선순위가 높은 요소를 찾아야하는데 이때 전체 배열을 순회해야하므로
O(n)의 시간복잡도가 소요 (단점)
2. Sorted Array
- 삽입시 정렬된 상태를 유지하기 위한 위치를 찾아 추가하므로
O(n)의 시간복잡도가 소요 (단점) - 단순히 배열을 순회하거나, 이진 탐색 등의 방법을 사용할 수 있음
- 삭제시 정렬된 순서에 따라 가장 마지막의 요소를 제거하면 되므로
O(1)의 시간복잡도가 소요 (장점)
앞선 Array와 Sorted Array에서의 장단점은 Linked List와 Sorted Linked List에서 동일하게 작용
3. Heap
- Heap이란 Complete Binary Tree의 한 종류로, Priority Queue를 위해 만들어진 자료 구조
- 모든 요소가 완벽히 정렬되어 있지는 않지만, 그렇다고 완전히 정렬되지 않은 것도 아님
→ 거의 정렬된 상태를 가짐 - 삽입과 삭제시 모두
O(log₂n)의 시간 복잡도를 가지므로 앞선 구현 방식에 비해 노드의 개수가 많아질수록 유리
Heap
개념
- 여러 값들 중 가장 큰 값이나 가장 작은 값을 빨리 찾기에 유리
- 자식 노드들이 부모 노드보다 작다는 규칙만 유지하면 됨
- Binary Search Tree에서는 중복되는 값을 서용하지 않았지만 Heap은 중복되는 값을 허용
- 큰 값은 높은 Level에 작은 값은 낮은 Level에 위치해 느슨하게 정렬된 상태를 달성
- 기본적으로 Complete Binary Tree이므로 마지막 Level을 제외하고는 모두 채워져 있어야하며 왼쪽에서 오른쪽 순서로 채워져야함
구분
- Max heap: 각각의 부모 노드는 자식 노드보다 크거나 같음
- Min heap: 각각의 부모 노드는 자식 노드보다 작거나 같음
구현
- Binary Tree는 Array로 구현할 경우 빈 공간이 생겨 비효율적이지만 Heap은 그 특성상 빈 공간이 발생하지 않아 유리함
root노드는 배열의 1번에 저장됨- 각 노드의 인덱스는 새로운 노드가 추가되어도 바뀌지 않음
부모, 자식 노드의 인덱스 계산
현재 인덱스
i
부모 노드의 인덱스 :i/2
왼쪽 자식 노드의 인덱스 :i* 2
오른쪽 자식 노드의 인덱스 :i* 2 + 1
Insertion
- Upheap 방식을 사용 (상향식으로 비교)
- 새로운 요소를 추가할 때 가장 마지막 노드에 추가하고 부모 노드와 비교하며 자리를 바꿈
- Complete Binary Tree의 높이
h는log₂n이므로 삽입의 시간 복잡도는O(log₂n)
void insert(int key)
{
if (isFull()) return; // When the heap is full
int i = ++size; // Start from the position corresponding to the incremented heap size
// Traverse upward through the tree, comparing with parent nodes
// While the key is greater than the parent
while (i != 1 && key > getParent(i).getKey())
{
node[i] = getParent(i).getKey() ; // Move the parent node down
i /= 2; // Move up one level
}
node[i].setKey(key); // Final position: copy the data
}- 탐색하는 노드가
root가 아니고 부모 노드의 값보다 크다면 현재 위치에 부모 노드의 값을 저장하고 윗 레벨로 이동 - 부모 노드가 추가하려는 값보다 크다면 반복을 종료하고 해당 위치에 값을 저장
Deletion
- Downheap 방식을 사용(하향식으로 비교)
- 가장 마지막 노드를 root로 올리고 자리를 바꾸며 내려옴 (
root를 제거하므로) - Insertion과 동일하게
O(log₂n)의 시간 복잡도를 가짐
HeapNode remove() {
if( isEmpty() ) return NULL;
HeapNode root = node[1]; // Root node (the element to be removed)
HeapNode last = node[size--]; // The last node in the heap
int parent = 1; // Start Index
int child = 2; // Start Index's child(left)
while( child <= size ) // While not exceeding the heap boundary
{
if( child < size
&& getLeft(parent).getKey() < getRight(parent).getKey())
child++; // Select the larger child node
if( last.getKey() >= node[child].getKey() ) break;
// Move down one level
node[parent] = node[child];
parent = child;
child *= 2;
}
node[parent] = last; // Place the last node in its final position
return root; // Return the root node
}root노드의 값을root에, 마지막 노드의 값을last에 저장root노드는 1에서 시작하므로parent는 1을 갖고child는 왼쪽 Subtree를 기준으로 하여 2로 설정- heap 영역 안에 있는 동안
while문 내부 로직을 반복 child를 설정할 때 더 큰 자식 노드를 선택하기 위해 오른쪽 자식 노드가 더 크다면 기존child값에 1을 더함last노드에 저장된 값이 선택된 자식 노드의 값보다 크거나 같다면 반복을 종료- 그렇지 않다면 부모 위치에 자식 노드로 자리를 바꾸고 바꾼 자식 노드를 기준으로 반복을 실시
