우선순위 큐
우선순위 큐(priority queue)는 모든 데이터가 우선순위를 갖고 있고, 들어온 순서와 상관 없이 우선순위가 높은 데이터가 먼저 출력되는 구조. (보통의 큐는 FIFO 구조)
우선순위 큐는 컴퓨터의 네트워크 트래픽 제어, 운영체제에서의 작업 스케줄링 등에서 활용.
우선순위 큐를 구현하는 가장 효율적인 구조는 힙(heap).
- 우선순위 큐의 연산
우선순위 큐에서도 가장 중요한 연산은 삽입, 삭제.
삭제연산에서 어떤 요소가 먼저 삭제되는가에 따라 최소 우선순위 큐 / 최대 우선순위 큐 로 나눈다.
- 최대 우선순위 큐 : 우선순위가 가장 높은 요소가 먼저 삭제.
- 최소 우선순위 큐 : 우선순위 가장 낮은 요소를 먼저 삭제.
-> 최대 우선순위 큐의 delete() : 가장 우선순위가 높은 요소를 꺼내서 반환.
힙을 사용해 우선순위 큐 구현
힙(heap)은 완전 이진트리의 일종으로 우선순위 큐를 위해 만들어진 자료구조.
힙은 반 정렬 상태를 유지.
-> 요소들이 완전히 정렬된 것은 아니지만 전혀 정렬되지 않은 것도 아닌 상태를 이용해 우선순위 큐를 구현.
힙을 사용해 구현한 우선순위 큐의 시간 복잡도 : 삽입, 삭제 모두 O(log₂n) -> 효율적
- 힙
힙은 여러 개의 값들 중에서 가장 큰 값이나 가장 작은 값을 빠르게 찾아내도록 만든 자료구조.
힙은 부모 노드의 키 값이 자식 노드의 키 값보다 항상 큰(또는 작은) 이진트리.
이진탐색트리와는 달리 힙 트리는 중복된 값을 허용한다.
힙은 큰 값이 상위 레벨에 있고 작은 값이 하위 레벨에 있다는 정도의 느슨한 정렬 상태를 유지.
-> 힙의 목적이 삭제 연산에서 가장 큰 값(또는 작은)을 효율적으로 찾아내기만 하면 되기 때문에 전체 정렬할 필요X.
- 최대 힙(max heap) : 부모 노드의 키 값이 자식 노드의 키 값보다 크거나 같은 완전 이진트리
- 최소 힙(min heap) : 부모 노드의 키 값이 자식 노드의 키 값보다 작거나 같은 완전 이진트리
- 배열을 이용한 힙 구현 ( 최대 힙 )
힙은 완전이진트리이기 때문에 차례대로 번호를 붙일 수 있고 각각의 노드 중간에 비어 있는 요소가 없다.
이 번호를 배열의 인덱스로 생각. ( 편의를 위해 첫번째 인덱스 0은 사용 X )
트리의 모든 위치의 노드 번호는 새로운 노드가 추가되더라도 변하지 않는다. ( 루트 노드의 왼쪽 자식 번호는 항상 2번, 오른쪽 자식은 항상 3번 )
- 왼쪽 자식의 인덱스 = (부모 인덱스) * 2
- 오른쪽 자식의 인덱스 = (부모 인덱스) * 2 + 1
- 부모의 인덱스 = (자식 인덱스) / 2
- 힙의 연산
- 삽입 연산
힙에 새로운 요소가 들어오면, 일단 새로운 노드를 힙의 마지막 노드의 다음 위치에 삽입.
삽입 후에 새로운 노드를 부모 노드들과 교환해서 힙의 성질을 만족시켜 주는 과정이 필요하다. = 업힙(up-heap)
// 최대 힙 트리 삽입 연산
void insert_heap(HNode n) {
if (is_full_heap())
return;
int idx = ++heap_size; // 힙 크기 하나 증가시킴
while (idx != 1 && Key(n) > Parent(idx)) { // idx가 루트노드가 아니고, n의 Key가 idx(삽입 위치)의 부모보다 크면(최대힙 성질 맞추기)
heap[idx] = Parent(idx); // 삽입한 새 노드를 부모노드로 교환 -> 최대 힙 성질 맞추기
idx /= 2; // 부모 인덱스 = 자식인덱스 / 2
}
heap[idx] = n;
}
- 삭제 연산
힙에서 삭제 연산은 루트 노드를 삭제하는 것!
최대 힙에서는 루트가 최댓값을 가지므로
루트노드를 삭제하고 힙의 성질을 계속 유지하기 위해 힙 트리를 재구성해야 한다.
루트노드가 비게 되면 마지막 노드를 루트 자리로 올린 다음에 순차적으로 강등시킨다. = 다운힙(down-heap)
- 루트 노드를 삭제하고 빈 루트 노드 자리에 힙의 마지막 노드를 가져온다.
- 새로운 루트와 자식 노드들을 비교하면 자식 노드가 더 크기 때문에 교환이 일어난다. 이때, 자식 중에서 더 큰 노드와 비교하고 교환해야 한다.
- 자식 노드보다 더 작지 않을 때 까지 교환
// 최대 힙 트리 삭제 연산
HNode delete_heap() {
if (is_empty_heap)
{
printf("힙 트리 공백\n");
return -1;
}
HNode hRoot = heap[1]; // 루트 노드 복사(0은 인덱스 편의상 비워둠)
HNode last = heap[heap_size--]; // 마지막 노드 복사
int parentIdx = 1; // parentIdx를 루트로 초기화
int childIdx = 2; // childIdx를 왼쪽 자식 위치로 초기화
while (childIdx <= heap_size) // 힙 트리를 벗어나지 않는 동안
{
if (childIdx < heap_size && Key(Left(parentIdx)) < Key(Right(parentIdx))) { // 왼쪽 자식이 오른쪽 자식보다 작으면
childIdx++; // 처음 왼쪽 자식 위치로 설정해두고 오른쪽 자식이 더 크면 +1
}
if (Key(last) >= Key(childIdx)) // 마지막 노드가 더 큰 자식보다 크면 이동 완료.
break;
heap[parentIdx] = heap[childIdx];
parentIdx = childIdx;
childIdx *= 2; // 아니면 한단계 아래로 이동
}
heap[parentIdx] = last; // 마지막 노드를 최종 위치에 저장
return hRoot;
}
- 힙의 삽입/삭제 연산의 시간 복잡도
힙은 완전이진트리이므로 힙의 높이는 log₂n.
- 삽입 연산 : 새로운 요소가 부모 노드와 교환을 하는 업힙 과정을 거치면서 최악의 경우, 루트노드 까지 올라가야 하므로 트리의 높이에 해당하는 비교 연산 및 이동 연산이 필요하다.
- 삭제 연산 : 마지막 노드를 루트로 가져온 후 자식 노드들과 비교 교환하는 다운힙 과정을 거치면서 최악의 경우, 가장 아래 레벨까지 내려가야 하므로 역시 트리의 높이만큼 시간이 걸림.
따라서 힙의 삽입/삭제 연산의 시간 복잡도는 O(log₂n).
- 배열을 이용한 힙 구현 ( 최대 힙 ) 전체 코드
#include <iostream>
#define MAX_HEAP_NODE 200
typedef int HNode;
#define Key(n) (n) // 힙 노드의 우선순위 값을 반환하는 매크로 함수
HNode heap[MAX_HEAP_NODE];
int heap_size;
#define Parent(i) heap[i/2] // i의 부모 노드
#define Left(i) heap[i*2] // i의 왼쪽 자식 노드
#define Right(i) heap[i*2+1] // i의 오른쪽 자식 노드
using namespace std;
void init_heap() { heap_size = 0; }
bool is_empty_heap() { return (heap_size == 0); }
bool is_full_heap() { return (heap_size == MAX_HEAP_NODE - 1); }
HNode find_heap() { return heap[1]; } // 힙에서 루트 노드 반환 함수
// 최대 힙 트리 삽입 연산
void insert_heap(HNode n) {
if (is_full_heap())
return;
int idx = ++heap_size; // 힙 크기 하나 증가시킴
while (idx != 1 && Key(n) > Parent(idx)) { // idx가 루트노드가 아니고, n의 Key가 idx(삽입 위치)의 부모보다 크면(최대힙 성질 맞추기)
heap[idx] = Parent(idx); // 삽입한 새 노드를 부모노드로 교환 -> 최대 힙 성질 맞추기
idx /= 2; // 부모 인덱스 = 자식인덱스 / 2
}
heap[idx] = n;
}
// 최대 힙 트리 삭제 연산
HNode delete_heap() {
if (is_empty_heap())
{
printf("힙 트리 공백\n");
return -1;
}
HNode hRoot = heap[1]; // 루트 노드 복사(0은 인덱스 편의상 비워둠)
HNode last = heap[heap_size--]; // 마지막 노드 복사
int parentIdx = 1; // parentIdx를 루트로 초기화
int childIdx = 2; // childIdx를 왼쪽 자식 위치로 초기화
while (childIdx <= heap_size) // 힙 트리를 벗어나지 않는 동안
{
if (childIdx < heap_size && Key(Left(parentIdx)) < Key(Right(parentIdx))) { // 왼쪽 자식이 오른쪽 자식보다 작으면
childIdx++; // 처음 왼쪽 자식 위치로 설정해두고 오른쪽 자식이 더 크면 +1
}
if (Key(last) >= Key(heap[childIdx])) // 마지막 노드가 더 큰 자식보다 크면 이동 완료.
break;
heap[parentIdx] = heap[childIdx];
parentIdx = childIdx;
childIdx *= 2; // 아니면 한단계 아래로 이동
}
heap[parentIdx] = last; // 마지막 노드를 최종 위치에 저장
return hRoot;
}
void print_heap() {
for (int i = 1,level = 1; i <= heap_size; ++i) {
if (i == level) {
printf("\n");
level *= 2;
}
printf("%2d ", Key(heap[i]));
}
printf("\n-----------");
}
void main() {
// 최대 힙 트리 테스트
init_heap();
// 8개의 노드 삽입
insert_heap(2);
insert_heap(5);
insert_heap(4);
insert_heap(8);
insert_heap(9);
insert_heap(3);
insert_heap(7);
insert_heap(3); // 중복삽입
print_heap();
// 삭제 연산 실행 후 힙트리 출력
delete_heap();
print_heap();
delete_heap();
print_heap();
printf("\n");
}
- 매크로 함수
e.g.) #define Key(n) (n)
매크로 함수는 함수처럼 인자를 설정할 수 있는 매크로를 의미. 매크로 함수라고 부르지만 단순히 치환하기만 하므로 실제로 함수는 아닙니다. 함수 선언과 비슷하지만 매크로 함수는 인자의 자료형을 신경 쓰지 않습니다. 즉, 자료형의 독립성을 보장합니다. 또 매크로 함수 내부에서 자기 자신을 호출할 수 없다는 특징이 있습니다.
* #define은 전처리 과정에서 치환되므로 메모리 공간 할당되지 않는다.
힙의 응용: 힙 정렬
힙을 이용하면 데이터를 간단하게 정렬 가능. 힙 정렬은 힙을 사용하는 정렬 알고리즘.
- n개의 요소를 하나씩 힙에 삽입 --> nlog₂n만큼 시간 소요
- 힙에서 n번에 걸쳐 하나씩 요소들을 삭제하고 출력 --> nlog₂n만큼 시간 소요
정렬에 필요한 전체시간은 nlog₂n + nlog₂n 에 비례.
따라서 힙 정렬의 시간복잡도는 O(nlog₂n) 이다.
삽입 정렬 같은 대부분의 간단한 정렬 알고리즘이 O(n^2)인 것을 생각하면 매우 효율적.
힙 정렬은 특히 전체 자료를 정렬하는 것이 아니라 전체에서 가장 큰 값 몇 개만 필요할 때 가장 유용.
- 구현 코드
위의 최대 힙 트리 구현 코드를 이용.
#include <iostream>
#define MAX_HEAP_NODE 200
typedef int HNode;
#define Key(n) (n) // 힙 노드의 우선순위 값을 반환하는 매크로 함수
HNode heap[MAX_HEAP_NODE];
int heap_size;
#define Parent(i) heap[i/2] // i의 부모 노드
#define Left(i) heap[i*2] // i의 왼쪽 자식 노드
#define Right(i) heap[i*2+1] // i의 오른쪽 자식 노드
using namespace std;
void init_heap() { heap_size = 0; }
bool is_empty_heap() { return (heap_size == 0); }
bool is_full_heap() { return (heap_size == MAX_HEAP_NODE - 1); }
HNode find_heap() { return heap[1]; } // 힙에서 루트 노드 반환 함수
// 최대 힙 트리 삽입 연산
void insert_heap(HNode n) {
if (is_full_heap())
return;
int idx = ++heap_size; // 힙 크기 하나 증가시킴
while (idx != 1 && Key(n) > Parent(idx)) { // idx가 루트노드가 아니고, n의 Key가 idx(삽입 위치)의 부모보다 크면(최대힙 성질 맞추기)
heap[idx] = Parent(idx); // 삽입한 새 노드를 부모노드로 교환 -> 최대 힙 성질 맞추기
idx /= 2; // 부모 인덱스 = 자식인덱스 / 2
}
heap[idx] = n;
}
// 최대 힙 트리 삭제 연산
HNode delete_heap() {
if (is_empty_heap())
{
printf("힙 트리 공백\n");
return -1;
}
HNode hRoot = heap[1]; // 루트 노드 복사(0은 인덱스 편의상 비워둠)
HNode last = heap[heap_size--]; // 마지막 노드 복사
int parentIdx = 1; // parentIdx를 루트로 초기화
int childIdx = 2; // childIdx를 왼쪽 자식 위치로 초기화
while (childIdx <= heap_size) // 힙 트리를 벗어나지 않는 동안
{
if (childIdx < heap_size && Key(Left(parentIdx)) < Key(Right(parentIdx))) { // 왼쪽 자식이 오른쪽 자식보다 작으면
childIdx++; // 처음 왼쪽 자식 위치로 설정해두고 오른쪽 자식이 더 크면 +1
}
if (Key(last) >= Key(heap[childIdx])) // 마지막 노드가 더 큰 자식보다 크면 이동 완료.
break;
heap[parentIdx] = heap[childIdx];
parentIdx = childIdx;
childIdx *= 2; // 아니면 한단계 아래로 이동
}
heap[parentIdx] = last; // 마지막 노드를 최종 위치에 저장
return hRoot;
}
void print_heap() {
for (int i = 1,level = 1; i <= heap_size; ++i) {
if (i == level) {
printf("\n");
level *= 2;
}
printf("%2d ", Key(heap[i]));
}
printf("\n-----------");
}
// 정렬을 위한 배열 출력
void print_array(int a[], int n, const char* msg) {
printf("%10s: ", msg);
for (int i = 0; i < n; ++i) {
printf("%3d", a[i]);
}
printf("\n");
}
void main() {
int data[10];
for (int i = 0; i < 10; ++i)
data[i] = rand() % 100;
print_array(data, 10, "정렬 전");
// 최대 힙을 이용한 힙 정렬
init_heap();
for (int i = 0; i < 10; ++i)
insert_heap(data[i]);
for (int i = 9; i >= 0; --i) { // 최대힙이라 삭제 연산에서 나오는 값을 배열의 뒤쪽부터 저장
data[i] = Key(delete_heap());
}
print_array(data, 10, "정렬 후");
}
'코딩테스트 및 개인공부 > 자료구조' 카테고리의 다른 글
| [자료구조] [9] 이진탐색트리 (0) | 2021.12.30 |
|---|---|
| [자료구조] [8] 트리 (0) | 2021.12.29 |
| [자료구조] [7] 순환 (0) | 2021.12.29 |
| [자료구조] [6] 리스트 (0) | 2021.12.09 |
| [자료구조] [5] 포인터, 연결리스트 (0) | 2021.12.08 |
