반응형
1. 우선순위 큐 란?
: 우선 순위를 가진 항목들을 저장하는 큐이다.
우선 순위가 높은 데이터가 먼저 삭제된다.
1) 구현 방법
- 배열 이용
- 연결 리스트 이용
- 힙(Heap) 이용 -> 가장 효율적이다.(트리 구조)
2. 힙(Heap) 이란?
: 노드들이 아래의 식을 만족하는 완전이진트리이다.
key(부모 노드) >= key(자식 노드)
* 완전이진트리 : 왼쪽부터 차례대로 이진트리를 꽉 채운 트리이다.
1) 힙의 종류
- 최대 힙 : key(부모 노드) >= key(자식 노드)
- 최소 힙 : key(부모 노드) <= key(자식 노드)
2) 힙의 높이
: N 개의 노드를 가지고 있는 힙의 높이는 O(logN) 이다.
3) 힙의 구현방법
: 배열로 구현한다. 완전이진트리이므로 각 노드에 번호를 붙일 수 있다. 이 번호를 배열의 인덱스로 생각한다.
* 배열로 트리구조 구현할 때 장점 - 부모노드를 쉽게 찾을 수 있다.
왼쪽 자식 인덱스 = (부모의 인덱스) * 2
오른쪽 자식 인덱스 = (부모의 인덱스) * 2 + 1
부모의 인덱스 = (자식의 인덱스) / 2
4) 기본 코드
#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;
}
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 preorder1(HeapType *h, int root){
if(root > h->heap_size)
return;
printf("%d ", h->heap[root].key);
preorder1(h, root * 2);
preorder1(h, root * 2 + 1);
}
void print_heap(HeapType *h){
int num = 4;
printf("%d\n", h->heap[1].key);
for(int i=2; i<=h->heap_size; i++){
printf("%d ", h->heap[i].key);
if((i+1) == num){
printf("\n");
num *= 2;
}
}
printf("\n");
}
int max(int a, int b){
if (a >= b)
return a;
else
return b;
}
int find(HeapType *h, int root, int key){
if(root > h->heap_size)
return 0;
if(h->heap[root].key == key)
return root;
else if (h->heap[root].key < key) // 중요
return 0;
return max(find(h, root * 2, key), find(h, root * 2 + 1, key)); // 중요
}
void print_sorted_value(HeapType *h){
int size = h->heap_size;
element e[10];
for(int i=0; i< size; i++){
e[i] = delete_max_heap(h);
printf("%d ", e[i].key);
}
for(int i=0; i< size; i++){
insert_max_heap(h, e[i]);
}
printf("\n");
}
void modify_priority(HeapType *h, int oldKey, int newKey){
int i, child;
if(oldKey == newKey)
return;
i = find(h, 1, oldKey);
if(i == 0)
return;
if(newKey > oldKey){
while ((i != 1) && (newKey > h->heap[i / 2].key)) {
h->heap[i] = h->heap[i / 2];
i /= 2;
}
h->heap[i].key = newKey; // ªı∑ŒøÓ ≥εÂ∏¶ ª¿‘
} else {
element temp = h->heap[(h->heap_size)];
child = i * 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[i] = h->heap[child];
i = child;
child *= 2;
}
h->heap[i] = temp;
}
}
int main(void)
{
element e1 = { 10 }, e2 = { 5 }, e3 = { 30 };
element eA = { 9 }, eB = { 19 }, eC = { 39 };
element e4, e5, e6;
int index;
int key, oldKey, newKey;
HeapType* heap;
heap = create();
init(heap); // √ ±‚»≠
printf("Step1 : 삽입된 10, 5, 30에 추가적으로 9, 19, 39를 삽입한다\n");
insert_max_heap(heap, e1);
insert_max_heap(heap, e2);
insert_max_heap(heap, e3);
insert_max_heap(heap, eA);
insert_max_heap(heap, eB);
insert_max_heap(heap, eC);
printf("\nStep2 : preorder, print_heap 함수 테스트\n");
preorder1(heap, 1);
printf("\n");
print_heap(heap);
e4 = delete_max_heap(heap);
printf("삭제 : %d 루트가 삭제됨\n", e4.key);
print_heap(heap);
printf("\nStep3 : find 함수 테스트\n");
printf("찾을 key 입력(-1 for exit) : ");
scanf("%d", &key);
while(key != -1){
if((index = find(heap, 1, key)) == 0)
printf("%d는 없음\n", key);
else
printf("%d은 [%d]에 있음\n", key, index);
printf("찾을 key 입력(-1 for index) : ");
scanf("%d", &key);
}
printf("\nStep4 : print_sorted_value 함수 테스트\n");
print_sorted_value(heap);
printf("\nStep5 : modify_priority 함수 테스트\n");
printf("바꿀 key 입력(-1 for exit) : ");
scanf("%d", &oldKey);
while(oldKey != -1){
printf("새 key 입력 : ");
scanf("%d", &newKey);
modify_priority(heap, oldKey, newKey);
print_heap(heap);
printf("바꿀 key 입력(-1 for exit) : ");
scanf("%d", &oldKey);
}
free(heap);
return 0;
}
5) 삽입 연산
- 힙의 마지막 노드에 이어서 삽입한다.
- 삽입 후에 새로운 노드를 부모 노드들과 교환해서 힙의 성질을 만족시킨다.
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; // ªı∑ŒøÓ ≥εÂ∏¶ ª¿‘
}
6) 삭제 연산
- 루트 노드를 삭제한다.
- 마지막 노드를 루트 노드로 이동시킨다.
- 루트에서부터 단말 노드까지의 경로에 있는 노드들을 교환하여 힙의 성질을 만족시킨다.
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;
}
7) Find 연산
int find(HeapType *h, int root, int key){
if(root > h->heap_size)
return 0;
if(h->heap[root].key == key)
return root;
else if (h->heap[root].key < key) // 중요
return 0;
return max(find(h, root * 2, key), find(h, root * 2 + 1, key)); // 중요
}
- 기준 인덱스가 힙의 크기보다 크면 이미 힙을 초과한 것이므로 0을 반환한다.
- 키 값이 동일하면 기준 인덱스를 반환한다.
- 기준 노드의 값이 찾는 값보다 작으면 그 밑으로는 더 작은 값들밖에 없기 때문에 더 이상 값을 찾을 수 없으므로 0을 반환한다.
- 서브트리의 왼쪽과 오른쪽 노드에 find 연산을 수행하고 둘 중 큰 값을 반환한다.
값을 찾을 수 없는 경우 0을 반환하기 때문에 둘 중 큰 값을 반환하는 것이다.
3. 힙 정렬
- 하나의 요소를 힙에 삽입하거나 삭제할 때 시간이 O(logN)만큼 소요된다. 요소의 개수가 n개이므로 전체적으로 O(nlogN) 시간이 걸린다. (빠른 편)
- 힙 정렬이 최대로 유용한 경우는 가장 큰 값 몇 개만 필요할 때이다.
반응형
'Computer Science > Data Structure' 카테고리의 다른 글
| 자료구조 3 - 4) 그래프 최단경로 : 다익스트라, 플로이드 / 위상 정렬 (0) | 2020.12.10 |
|---|---|
| 자료구조 3 - 3) 그래프 MST : 크루스칼, 프림 (0) | 2020.12.05 |
| 자료구조 3 - 2) 그래프 BFS, DFS (0) | 2020.12.05 |
| 자료구조 3 - 1) 그래프 (0) | 2020.12.04 |
| 자료구조 1. 이진 탐색 트리, 쓰레드 이진 트리 (0) | 2020.12.04 |
