큐
- 큐(priority queue)에서는 데이터들이 두선 순위를 가지고 있고 우선순위가 높은 데이터가 먼저 나가게 된다. 보통 큐에서는 가장 먼저 들어간 데이터가 먼저 나온다.
| 자료스택 | 삭제되는요소 |
| 스택 | 가장 최근에 들어온 데이터 |
| 큐 | 가장 먼저 들어온 데이터 |
| 우선순위 큐 | 가장 우선순위가 높은 데이터 |
> 우선순위 큐는 사실가장 일반저긴 큐이다. 왜냐하면 스택이나 큐도 우선순위 큐를 사용하면 얼마든지 구현할 수 있기 때문이다. 즉 적절한 우선순위만 부여하면 우선순위 큐는 스택이나 큐로 동작할 것이다.
create()::=우선순위 큐를 생성
init(q)::=우선순위 큐q를 초기화
is_empty(q)::=우선순위 큐q가 비어있는지 검사
is_full(q)::=우선순위 큐q가 가득 찼는지 검사
insert(q,x)::=우선순위 큐q에 요소 x를 추가
delete(q)::=우선선위 큐로부터 가장 우선순위가 높은 요소를 삭제하고 이 요소를 반환
find(q)::=우선순위가 가장 높은 요소를 반환- 큐는 0개 이상의 요소 모임이다. 각 요소들은 우선순위값을 가지고 있으며 가장 중요한 연산은 insert연산, delet연산이다. 우선순위 큐는 2가지로 구분할 수 있는데, 최소 우선순위 큐는 가장 우선순위가 낮은 요소를 삭제한다. 최대 우선순위 큐는 가장 우선순위가 높은 요소가 먼저 삭제된다.
우선순위 큐의 구현방법
- 배열을 사용하는 방법
> 정렬이 안된 배열을 사용하게 되면 삽입은 간단하다. 배열의 맨 끝에 새로운 요소를 추가하면 된다. 따라서 삽입의 시간복잡도는 O(1)이다.
> 삭제할 때는 가장 우선순위가 높은 요소를 찾아야 한다. 정렬이 안되어 있으므로 처음부터 끝가지 모든 요소를 스캔해야 한다. 삭제의 복잡도는 O(n)이 된다. 그리고 요소가 삭제된 다음 뒤에 있는 요소들을 앞으로 이동시켜야 하는 부담도 있다.
> 정렬이 되있는 배열의 경우 새로운 요소를 삽입할 때는 다른 요소와 값을 비교하여 적절한 삽입 위치를 결정해야 한다. 삽입 위치를 찾기 위해서 순차 탐색이나 이진탐색과 같은 방법을 이용할 수 있다. 삽입 위치를 찾은 다음 삽입 위치 뒤에 있는 요소들을 이동시켜서 빈자리를 만든 다음, 삽입해야 한다. 따라서 삽입시 시간복잡도는 일반적으로 O(n)이다.
> 삭제시에는 숫자가 높은 것이 우선순위가 높다고 가정하면 맨 뒤에 위치한 요소들을 삭제하면 된다. 삭제의 경우 시간복잡도는 O(1)이다.
- 연결 리스트를 사용하는 방법
> 정렬이 안된 리스트라면 삽입 시에 첫 번째 노드로 삽입시키는 것이 유리하다. 삽입 시에 배열과 달리 다른 노드를 이동할 필요가 없다. 포인터만 이동하면 된다. 따라서 삽입의 시간복잡도는 O(1)이다
> 삭제시에는 포인터를 따라서 모든 노드를 뒤져보아야 한다. 이 경우 시간복잡도는 O(n)이다
> 정렬 된 상태로 사용한다면, 우선순위가 높은 요소가 앞에 위치하는 것이 유리하다. 우선순위가 높은 요소가 첫 번째 노드가 되도록 한다. 삽입시에는 우선순위값을 기준으로 삽입위치를 찾아야 하므로 시간복잡도는 O(n)이 된다.
> 삭제시에는 첫 번째 노드를 삭제하면 되므로 O(1)이다
- 히프를 사용하는 방법
> 히프(heap)는 완전 이진트리의 일종으로 우선순위 큐를 위해서 특별히 만들어진 구조이다. 히프는 일종의 느슨한 정렬 상태를 유지한다. 완전히 정렬된 것은 아니지만 전혀 정렬이 안된 것도 아닌 상태를 유지한다. 히프는 이러한 느슨한 정렬 상황을 이용해서 우선순위 큐를 구현한다.
> 히프의 효율은 O(log2n)으로 다른 방법보다 상당히 유리하다.
| 표현방법 | 삽입 | 삭제 |
| 순서 없는 배열 | O(1) | O(n) |
| 순서 없는 연결리스트 | O(1) | O(n) |
| 정렬된 배열 | O(n) | O(1) |
| 정렬된 연결 배열 | O(n) | O(1) |
| 히프 | O(log n) | O(log n) |
히프
- 히프의 개념
> 히프는 완전이진트리 기반의 특정한 자료구조이다
- 히프는 여러개의 값들 중에서 가장 큰 값이나 가장 작은 값을 빠르게 찾아내도록 만들어진 자료구조이다. 부모노드의 키 값이 자식 노드의 키 값보다 항상 큰 이진트리이다
key(부모노드) >= key(자식노드)
> 히프 안에서 데이터들은 느슨한 정렬 상태를 유지한다. 큰 값이 상위 레벨에 있고 작은 값이 하위레벨에 있다.
> 히프의 목적은 삭제 연산이 수행될 때마다 가장 큰 값을 찾아내는 것이다. 따라서 전체를 정렬할 필요는 없다.
- 히프 종류
- 최대히프(max heap): 부모 노드의 키 값이 자식 노드의 키 값보다 크거나 같은 완전 이진트리
- 최소히프(min heap): 부모 노드의 키 값이 자식 노드의 키값보다 작거나 같은 완전 이진트리
- 히프 구현
> 히프는 완전이진트리이기 때문에 각각의 노드에 차례대로 번호를 붙일 수 있다. 번호를 배열의 인데 그로 생각하면 배열에 히프의 노드들을 저장할 수 있다. 따라서 히프를 저장하는 표준적인 자료구조는 배열이다
> 특정 위치의 노드 번호는 새로운 노드가 추가되어도 변하지 않는다. 루트 노드의 오른쪽 노드의 번호는 항상 3이다.
- 어떤 노드의 왼쪽이나 오른쪽 자식의 인덱스를 알고싶으면 아래의 식을 사용하면 된다.
왼쪽 자식의 인덱스 = (부모의 인덱스) * 2
오른쪽 자식의 인덱스 = (부모의 인덱스) * 2 + 1
- 부모의 인덱스를 알고 싶으면 아래의 식을 사용하면 된다
부모의 인덱스 = (자식의 인덱스) / 2
- 히프의 정의
#define MAX_ELEMENT 200
typedef struct{
int key;
}element;
typedef struct{
element heap[MAX_ELEMENT];
int heap_size;
}HeapType;
히프 생성
HeapType heap;
동적으로 히프 생성
HeapType *heap = creat();
- 삽입 연산
- 히프에 새로운 요소가 들어오면 일단 새로운 노드의 히프를 마지막 노드로 삽입한다.
- 마지막 노드 다음에 새로우 노드를 위치시키면 히프트리의 성질이 만족되지 않을 수 있다
- 삽입 후에 새로운 노드를 부모 노드들과 교환해서 히프의 성질을 만족시켜 주어야 한다
- 삭제연산
- 최대 히프에서 삭제 연산은 최대값을 가진 요소를 삭제하는 것이다
- 최대 히프에서 최대값은 루트노드이며 루트 노드가 삭제된다
- 루트 노드 삭제 후에 히프를 재구성하는 것이 필요하다
- 히프의 재구성이란 히프의 성질을 만족하기 위하여 위, 아래에 노드를 교환하는 것이다
- 전체 코드
#include <stdio.h>
#include <stdlib.h>
#define MAX_ELEMENT 200
typedef struct {
int key;
} element;
typedef struct {
element heap[MAX_ELEMENT];
int heap_size;
} HeapType;
// 생성 함수
HeapType* create()
{
return (HeapType*)malloc(sizeof(HeapType));
}
// 초기화 함수
void init(HeapType* h)
{
h->heap_size = 0;
}
// 현재 요소의 개수가 heap_size인 히프 h에 item을 삽입한다.
// 삽입 함수
void insert_max_heap(HeapType* h, element item)
{
int i;
i = ++(h->heap_size);
// 트리를 거슬러 올라가면서 부모 노드와 비교하는 과정
while ((i != 1) && (item.key > h->heap[i / 2].key)) {
h->heap[i] = h->heap[i / 2];
i /= 2;
}
h->heap[i] = item; // 새로운 노드를 삽입
}
// 삭제 함수
element delete_max_heap(HeapType* h)
{
int parent, child;
element item, temp;
item = h->heap[1];
temp = h->heap[(h->heap_size)--];
parent = 1;
child = 2;
while (child <= h->heap_size) {
// 현재 노드의 자식노드 중 더 작은 자식노드를 찾는다.
if ((child < h->heap_size) &&
(h->heap[child].key) < h->heap[child + 1].key)
child++;
if (temp.key >= h->heap[child].key) break;
// 한 단계 아래로 이동
h->heap[parent] = h->heap[child];
parent = child;
child *= 2;
}
h->heap[parent] = temp;
return item;
}
int main(void)
{
element e1 = { 10 }, e2 = { 5 }, e3 = { 30 };
element e4, e5, e6;
HeapType* heap;
heap = create(); // 히프 생성
init(heap); // 초기화
// 삽입
insert_max_heap(heap, e1);
insert_max_heap(heap, e2);
insert_max_heap(heap, e3);
// 삭제
e4 = delete_max_heap(heap);
printf("< %d > ", e4.key);
e5 = delete_max_heap(heap);
printf("< %d > ", e5.key);
e6 = delete_max_heap(heap);
printf("< %d > \n", e6.key);
free(heap);
return 0;
}
- 히프의 시간 복잡도
> 삽입 연산에서 새로운 요소 히프트리를 타고 올라가면 부모 노드들과 교환을 하는데, 최악의 경우 루트 노드까지 올라가야 하므로 트리의 높이에 해당하는 비교 연산 및 이동연산이 필요하다. 히프가 완전이진 트리임을 생각하면 히프의 높이는 log2n이 되고 따라서 삽입의 시간 복잡도는 O(log2 n)이 된다.
> 삭제는 마지막 노드를 루트로 가져온 후에 자식 노드들과 비교하여 교환하는 부분이 가장 시간이 걸리는 부분인데 이 역시 최악의 경우, 가장 아래 레벨까지 내려가야 하므로 트리의 높이만큼 시간이 걸린다. 따라서 삭제의 시간복잡도는 O(log2n0이 된다.
히프 정렬
- 최대 히프를 이용하면 정렬을 만들 수 있다. n개의 요소는 O(nl og2n)시간 안에 정렬된다.
> 한번에 하나씩 요소를 히프에서 꺼내서 배열의 뒤쪽부터 저장하면 배열요소들은 값이 증가되는 순서로 정렬되게 된다.
#include <stdio.h>
#include <stdlib.h>
#define MAX_ELEMENT 200
typedef struct {
int key;
} element;
typedef struct {
element heap[MAX_ELEMENT];
int heap_size;
} HeapType;
// 생성 함수
HeapType* create()
{
return (HeapType*)malloc(sizeof(HeapType));
}
// 초기화 함수
void init(HeapType* h)
{
h->heap_size = 0;
}
// 현재 요소의 개수가 heap_size인 히프 h에 item을 삽입
// 삽입 함수
void insert_max_heap(HeapType* h, element item)
{
int i;
i = ++(h->heap_size);
// 트리를 거슬러 올라가면서 부모 노드와 비교하는 과정
while ((i != 1) && (item.key > h->heap[i / 2].key)) {
h->heap[i] = h->heap[i / 2];
i /= 2;
}
h->heap[i] = item; // 새로운 노드를 삽입
}
// 삭제 함수
element delete_max_heap(HeapType* h)
{
int parent, child;
element item, temp;
item = h->heap[1];
temp = h->heap[(h->heap_size)--];
parent = 1;
child = 2;
while (child <= h->heap_size) {
// 현재 노드의 자식노드 중 더 작은 자식노드를 찾음
if ((child < h->heap_size) &&
(h->heap[child].key) < h->heap[child + 1].key)
child++;
if (temp.key >= h->heap[child].key) break;
// 한 단계 아래로 이동
h->heap[parent] = h->heap[child];
parent = child;
child *= 2;
}
h->heap[parent] = temp;
return item;
}
void heap_sort(element a[], int n)
{
int i;
HeapType* h;
h = create();
init(h);
for (i = 0; i<n; i++) {
insert_max_heap(h, a[i]);
}
for (i = (n - 1); i >= 0; i--) {
a[i] = delete_max_heap(h);
}
free(h);
}
#define SIZE 8
int main(void)
{
element list[SIZE] = { 23, 56, 11, 9, 56, 99, 27, 34 };
heap_sort(list, SIZE);
for (int i = 0; i < SIZE; i++) {
printf("%d ", list[i].key);
}
printf("\n");
return 0;
}
- 히프 정렬의 시간복잡도
> 히프트리 전체 높이가 거의 log2n이므로 하나의 요소를 히프에 삽입하거나 삭제할 때 히프를 재정비하는 시간이 log2n만큼 소모된다. 요소의 개수가 n개이므로 전체적으로 O(n log2 n)의 시간이 걸린다. 이 시간복잡도는 삽입 정렬 같은 간단한 정렬 알고리즘 O(n^2) 걸리는 것에 비하면 좋은 편이다.