- 참조 문헌 및 사이트(Reference)
Data Structure : A Pseudocode Approach with C
Data Structure and Algorithm in C++
이번 글에서는 우선순위큐(Priority Queue)에 대해서 알아보겠습니다.
우선순위큐도 C++ STL <queue>헤더에서 제공하는 컨테이너이며, 큐와 동일하게 push, pop, top이라는 연산이 있습니다. 다만, 일반 큐와는 다르게 동작합니다. 큐에서는 제일 먼저 들어왔던 데이터가 제일 먼저 삭제가 되었지만, 우선순위큐에서는 우선순위가 현재 우선순위큐 안에서 우선순위가 가장 높은 데이터가 먼저 삭제가 됩니다.
만약 값이 클수록 우선순위를 갖는 우선순위큐에 [ 8 78 19 45 23 56 32 ] 의 순서로 데이터를 삽입했을 때, pop 연산을 하게 되면 78이 나오게 됩니다. 따라서 [ 8 19 45 23 56 32 ] 가 남아있게 되고, 여기서 한번 더 pop 연산을 하게 되면 56이 나와서 [ 8 19 45 23 32 ]가 남게 됩니다.
우선순위큐도 큐처럼 리스트로 구현이 가능은 하지만, 보통은 힙(Heap)이라는 자료구조로 구현이 됩니다.
여기서 힙에 대해서 잠깐 설명을 하면, 힙은 이진트리의 한 종류입니다.
다만, 몇 가지 특징이 있는데, 아래와 같은 특징을 가지고 있습니다.
1. 힙은 완전 이진 트리이거나, 거의 완전 이진 트리이다.(complete or nearly complete)
여기서 완전 이진 트리는 leaf 노드를 제외한 모든 내부 노드가 두 개의 자식 노드를 갖는 트리를 말하며, 거의 완전 이진 트리는 마지막 레벨을 제외하고 모든 레벨이 채워져 있으며, 마지막 레벨에서는 가장 왼쪽 노드부터 채워져 있는 트리를 말합니다.
* 완전 이진 트리에 대한 게시글을 찾아보니, 완전 이진 트리를 제가 위에서 설명한 거의 완전 이진 트리와 동일한 의미로 사용하는 경우를 많이 봤는데, 혼용해서 사용하는 것 같습니다. 완전 이진 트리 개념이 거의 완전 이진 트리와 동일하게 사용될 때는, 제가 위에서 설명한 완전 이진 트리는 포화 이진 트리라고 부르고 있습니다.
2. 각 노드의 Key value는 자식 노드의 Key value보다 높은 우선순위를 가져야한다.
만약 우리가 높은 숫자가 더 높은 우선순위를 가지고 있다고 한다면, 각 노드의 값은 자식 노드의 값보다 무조건 큰 값이어야 한다는 의미입니다. 그리고 같은 부모 노드를 공유하는 자식 노드는 우선순위가 같습니다. 아래 그림과 같은 구조를 갖습니다.
위 예시들은 모두 힙이 아닙니다.
아까도 언급했지만, 힙은 C++ 라이브러리 <queue> 헤더에서 제공하고, priority_queue라는 이름으로 사용이 가능합니다. 기본적으로는 최대힙(maxheap)의 성질을 가지고 있으며, 우선순위 기준은 변경이 가능합니다.
힙의 기본 연산을 살펴봅시다.
첫 번째로는 데이터의 삽입 push 연산입니다.
위와 같은 트리가 있을 때, 25를 추가한다고 합시다. 힙에서 새로운 데이터를 추가할 때는 비어있는 첫 번째 자리에 우선 삽입이 됩니다. (a) 사진이 25라는 값의 첫 위치를 보여주고 있습니다. 그리고 부모노드와 비교해보니, 자식노드인 25가 부모노드 12보다 크므로, 두 노드의 위치를 바꾸어 줍니다. 그리고 다시 새로운 부모노드와 값을 비교해보니, 25가 더 크기 때문에 한 번더 자리를 바꿔줍니다. 다시 새로운 부모노드와 비교했더니 이번에는 부모노드보다 작기 때문에 push 연산이 종료됩니다. (이러한 동작을 reheapup 이라고 합니다)
이렇게 push 연산은 힙의 특징을 유지하면서 부모노드와 자리를 바꿔주는 연산을 반복하면 됩니다. 힙은 완전 이진 트리의 형태이기 때문에 최대로 가장 낮은 레벨에서 루트까지 수행될 수 있으므로 O(logN)의 시간복잡도를 가집니다.
서브트리들이 루트보다 무조건 값이 작기 때문에, 이렇게 바꾸는 연산을 진행해도 힙의 모습은 유지가 되므로 걱정할 필요는 없습니다.
다음으로는 pop과 top 연산입니다.
우선 top연산은 단순히 가장 높은 우선순위를 가진 값을 반환하면 됩니다. 이따가 구현할 때 언급하겠지만, 우리는 힙을 배열로 구현할 것이고, 배열의 첫 번째가 힙의 루트가 될 겁니다. 따라서 우리는 0번째 인덱스의 배열 값을 반환하면 쉽게 top에 위치한 값을 얻을 수 있습니다.
pop연산을 살펴봅시다.
위와 같은 힙이 있을 때, pop연산을 진행하면 가장 우선순위가 높은 78이라는 값이 삭제가 될 겁니다. 그림에서는 중간과정이 생략되어 있는데, 한 번 중간 과정을 살펴봅시다.
pop연산을 하게 되면, 첫 번째로는 힙의 루트와 힙의 가장 마지막 원소의 값을 바꿔줍니다. 따라서 78과 45의 위치가 서로 바뀌게 됩니다. 그리고 78은 삭제 처리가 되고, 우리는 이제 힙의 특성을 무시하고 있는 45의 위치를 제 위치로 돌리는 동작이 필요합니다.
삽입과는 반대로 이번에는 루트에서부터 시작해서 아래로 내려가면서 45의 위치를 맞추어주면 되는데 자식 노드 중에 큰 노드와 자리를 바꿔주는 연산을 반복하면 됩니다. 이 연산을 반복하면 결국 (b) 그림과 같이 45가 정상적인 위치를 찾게 됩니다. 자세한 것은 구현을 통해서 알아보도록 합시다.(위와 같은 연산을 reheapdown이라고 합니다)
위에서 언급했듯이 힙은 배열로 쉽게 구현이 가능합니다.(왼쪽부터 채워지기 때문에, 인덱스로 손쉽게 접근하는 것이 유용합니다)
전체코드입니다.
/* Heap.h */
#ifndef HEAP_H
#define HEAP_H
class HeapEmpty {};
class HeapFull {};
template<typename T>
class Heap
{
public:
Heap(int maxSize = 100) : n(0), maxSize(maxSize), heapData(new T(maxSize)) {}
~Heap() { delete heapData; }
void push(const T& data);
void pop();
T& top() const;
int size() const;
bool empty() const;
void print() const;
private:
T* heapData;
int n;
int maxSize;
};
template<typename T>
void Heap<T>::push(const T& data)
{
try {
if (size() == maxSize) throw HeapFull();
heapData[n] = data;
int parent = (n - 1) / 2;
int child = n;
while (parent >= 0 && heapData[parent] < heapData[child])
{
T tmp = heapData[parent];
heapData[parent] = heapData[child];
heapData[child] = tmp;
child = parent;
parent = (child - 1) / 2;
}
++n;
}
catch (HeapFull e) {
std::cout << "Heap is full\n";
exit(2);
}
}
template<typename T>
void Heap<T>::pop()
{
try {
if (empty()) throw HeapEmpty();
heapData[0] = heapData[--n];
int parent = 0;
int child = parent * 2 + 1;
bool placed = false;
while (!placed && child < n)
{
if (child < n - 1 && heapData[child] < heapData[child + 1])
child += 1;
if (heapData[parent] >= heapData[child])
placed = true;
else
{
T tmp = heapData[parent];
heapData[parent] = heapData[child];
heapData[child] = tmp;
}
parent = child;
child = parent * 2 + 1;
}
}
catch (HeapEmpty e) {
std::cout << "Heap is empty\n";
exit(2);
}
}
template<typename T>
T& Heap<T>::top() const
{
try {
if (empty()) throw HeapEmpty();
return heapData[0];
}
catch (HeapEmpty e) {
std::cout << "Heap is empty\n";
exit(2);
}
}
template<typename T>
int Heap<T>::size() const
{
return n;
}
template<typename T>
bool Heap<T>::empty() const
{
return (n == 0);
}
template<typename T>
void Heap<T>::print() const
{
std::cout << "[ ";
for (int i = 0; i < n; i++)
std::cout << heapData[i] << " ";
std::cout << "]\n";
}
#endif
push 연산부터 살펴봅시다.
template<typename T>
void Heap<T>::push(const T& data)
{
try {
if (size() == maxSize) throw HeapFull();
heapData[n] = data;
int parent = (n - 1) / 2;
int child = n;
while (parent >= 0 && heapData[parent] < heapData[child])
{
T tmp = heapData[parent];
heapData[parent] = heapData[child];
heapData[child] = tmp;
child = parent;
parent = (child - 1) / 2;
}
++n;
}
catch (HeapFull e) {
std::cout << "Heap is full\n";
exit(2);
}
}우선 push가 되면 데이터를 마지막 위치에 삽입합니다.
그리고 이제 부모노드와 값을 비교하며 바꿔주는 연산을 진행하면 되는데, 배열로 구현되어 있기 때문에 우리는 인덱스로 각 노드에 접근을 할겁니다.
루트의 인덱스는 0이고, 루트의 자식 노드의 인덱스는 1, 2가 됩니다. 아래와 같은 구조처럼 인덱스가 할당되는 거죠.
일반화해보면, 부모 노드의 index가 n이라면, 자식 노드의 index는 (n * 2 + 1) 과 (n * 2 + 2)가 됩니다.
push에서는 자식노드의 값부터 시작해서 올라가야하므로, 반대로 자식노드가 n이라면 부모노드는 ((n - 1)/2)로 구할 수 있으며, 소수점은 버리면 됩니다. 따라서, 인덱스 5와 6의 부모노드 인덱스는 (5-1)/2와 (6-1)/2로 계산하면 2가 되고, 바로 이것이 인덱스 5와6의 부모노드의 인덱스가 됩니다. 그래서 while문을 통해서 자식노드와 부모노드의 값을 비교해가면서 자식노드가 더 크다면 바꿔주는 동작을 반복하며, 위치가 올바르다면 반복문을 빠져나와 연산을 마치게 됩니다.
pop연산도 유사합니다.
template<typename T>
void Heap<T>::pop()
{
try {
if (empty()) throw HeapEmpty();
heapData[0] = heapData[--n];
int parent = 0;
int child = parent * 2 + 1;
bool placed = false;
while (!placed && child < n)
{
if (child < n - 1 && heapData[child] < heapData[child + 1])
child += 1;
if (heapData[parent] >= heapData[child])
placed = true;
else
{
T tmp = heapData[parent];
heapData[parent] = heapData[child];
heapData[child] = tmp;
}
parent = child;
child = parent * 2 + 1;
}
}
catch (HeapEmpty e) {
std::cout << "Heap is empty\n";
exit(2);
}
}pop연산은 삭제할 데이터를 힙의 마지막 데이터와 바꿔준 다음에 힙 데이터 개수를 먼저 줄여줍니다. 이렇게 되면 삭제할 데이터는 이제 접근이 불가능하게 되는 거죠.
그리고 0번째 인덱스에 위치한 값들을 자식노드와 비교해가며 원래 자리를 찾아주는 연산을 하게 됩니다.
10번째 줄에서 child는 우선 부모노드 좌측에 위치한 노드의 인덱스로 설정해두고 반복문을 시작하게 됩니다.
그리고 같은 부모를 공유하는 자식노드들 간의 크기를 비교해서 더 큰 값의 노드와 부모노드의 값을 비교해서, 바꿔주는 동작을 반복합니다.
다만, 유의해야할 점은 마지막에 위치한 노드는 형제자매노드가 없을 수도 있습니다. 따라서 15번째 줄을 보게 되시면, 자식노드의 위치가 마지막 위치가 아닐 때만 자식노드끼리 비교해주게 됩니다.
using namespace std;
#include <iostream>
#include "Heap.h"
int main()
{
Heap<int> heap;
heap.push(8); heap.print();
heap.push(19); heap.print();
heap.push(23); heap.print();
heap.push(32); heap.print();
heap.push(45); heap.print();
heap.push(56); heap.print();
heap.push(78); heap.print();
heap.pop(); heap.print();
heap.pop(); heap.print();
heap.pop(); heap.print();
return 0;
}위와 같은 코드를 실행시켜보면 다음과 같은 결과를 얻을 수 있습니다.
0번째 배열은 항상 최대값을 가지게 되는 것을 볼 수 있죠.
한 가지 추가로 이야기 할 수 있는 것은 이 힙이라는 자료구조를 가지고, 힙 정렬(Heap Sort)를 구현해서 데이터를 정렬을 할 수 있습니다.
즉, 정렬되지 않은 데이터를 전부 힙에 추가를 한 다음에 pop을 하면서 순서대로 저장하면, 정렬이 되는 것이죠. 위에서는 최대힙을 구현했는데, 최소힙으로 힙 정렬을 구현해보도록 합시다. 최소힙은 pop할 때마다 가장 작은 값이 나오는 힙이며, 최소힙으로 힙정렬을 진행하면 내림차순으로 정렬이 됩니다.
그리고 방금 전에 봤던 코드를 조금 변경해서 사용할 수 도 있지만, 우리는 Sink라는 함수를 정의해서 힙정렬을 구현해봅시다. Sink함수는 pop함수와 같은 역할을 하는 함수입니다.
전체코드는 다음과 같습니다.
using namespace std;
#include <iostream>
#include <algorithm>
#include <vector>
void Sink(vector<int>& arr, int i, int n)
{
int parent = i, child = 2 * parent + 1;
bool placed = false;
while (!placed && child < n)
{
if (child < n - 1 && arr[child] > arr[child + 1])
child = child + 1;
if (arr[parent] < arr[child])
placed = true;
else
swap(arr[parent], arr[child]);
parent = child;
child = 2 * parent + 1;
}
}
void HeapSort(vector<int>& arr)
{
int n = arr.size();
for (int i = (n - 1) / 2; i >= 0; i--)
{
Sink(arr, i, n);
}
while (n > 0)
{
swap(arr[0], arr[n - 1]);
n = n - 1;
Sink(arr, 0, n);
}
}
int main()
{
vector<int> arr;
arr.push_back(5);
arr.push_back(10);
arr.push_back(56);
arr.push_back(25);
arr.push_back(78);
arr.push_back(13);
arr.push_back(9);
cout << "정렬전 배열 : ";
for (int i = 0; i < arr.size(); i++)
{
cout << arr[i] << " ";
}
cout << "\n";
HeapSort(arr);
cout << "정렬후 배열 : ";
for (int i = 0; i < arr.size(); i++)
{
cout << arr[i] << " ";
}
cout << "\n";
return 0;
}HeapSort의 알고리즘을 우선 설명드리면, 우선 배열의 마지막 원소의 부모노드부터 Sink함수를 수행합니다.
아래와 같은 원소가 있을 때, 56부터 Sink 함수를 시작해서 최소힙의 구조를 만듭니다.
2, 1, 0 인덱스에 대해서 Sink함수를 모두 수행하면 아래와 같이 됩니다. 운이 좋게도 56과 9의 위치만 변경이 됬네요.
다음으로는 배열의 첫 번째 원소를 뒤로 위치시키면서 힙의 크기를 감소시켜 최소힙을 다시 유지시켜주는 동작을 진행합니다. 따라서 0번째 인덱스의 배열값을 마지막 위치의 값과 변경해서 0번째 인덱스에 대해서 Sink함수를 수행하면 됩니다. 여기서는 첫번째 원소인 5와 마지막 원소인 56가 위치가 서로 바뀌겠죠.
그리고 최소힙을 다시 유지시키기 위해서 첫 번째 배열에 대해서 Sink를 진행하지만, 여기서 우리는 최소힙의 크기를 감소시켰기 때문에 마지막에 있는 5는 영향을 받지 않습니다. 진행하면 다음과 같이 됩니다.
다시 첫번째 배열값을 마지막 배열과 바꿔주고 Sink를 진행하면 아래와 같이 됩니다.
힙의 크기가 0이 될때까지 반복해주면 결과적으로 아래와 같이 됩니다.
배열로 나타내면 결국 내림차순으로 [ 78 56 25 13 10 9 5 ], 이렇게 정렬이 됩니다. 실행해보면 다음과 같은 결과를 얻을 수 있습니다.
힙정렬의 시간복잡도는 O(nlogn)이 됩니다. 시간복잡도 구하는 것이 꽤나 복잡한데, 나중에 한 번 다루어 봐야겠습니다.
우선순위큐를 설명하면서 힙 설명이 길어졌는데, 우선순위큐는 이렇게 구현이 됩니다. 평소에는 아마 라이브러리에서 제공하는 것을 쓰면 되겠습니다. 기회가 되면 관련 문제들을 같이 풀어보도록 하겠습니다.
'Data Structure & Algorithm > 자료구조' 카테고리의 다른 글
| [자료구조] Directed Graph (0) | 2021.10.04 |
|---|---|
| [자료구조] Binary Search Tree(BST) (0) | 2020.09.09 |
| [자료구조] 트리(Tree) (0) | 2020.09.03 |
| [자료구조] Queue(큐), Deque(덱) (0) | 2020.09.01 |
| [자료구조] Stack(스택) (0) | 2020.08.31 |
댓글