-
우선순위 큐
먼저 들어간 요소가 먼저 나오는(First-In First Out)자료구조를 일컫어 '큐(Queue)'라고 한다. 우선순위 큐(Priority Queue)도 보통의 큐처럼 동작하지만 '우선순위' 속성을 갖는 데이터를 다룬다는 것이 다르다.
우선순위 큐의 삽입 연산
우선순위 큐의 삽입(Enqueue)은 요소의 우선순위 오름차순으로 연결된다.
새로운 요소가 삽입될 때 우선순위를 비교하여 새로운 요소가 들어가야할 자리에 삽입된다.
우선순위 큐의 제거 연산
우선순위 큐의 제거(Dequeue) 연산은 전단만 제거하면 된다.
우선순위 큐의 구현
다음에 나오는 힙을 배우고 구현
-
힙
여기서 말하는 힙은 프로그래밍에서 말하는 자유저장소(Free Store)가 아니라, 힙 순서 속성(Heap Order Property)을 만족하는 완전 이진 트리이다.
완전 이진 트리는 최고 깊이를 제외한 모든 깊이의 노드들이 완전히 채워져 있는 이진 트리이다.
힙 순서 속성이란 트리 내의 모든 노드가 부모 노드보다 커야 한다는 규칙이다.
위 그림은 힙 순서를 만족하는 완전 이진트리, 즉 힙의 예이다
힙의 노드들은 그저 자식 노드가 부모 노드보다 커야 한다는조건만 만족시키기 때문이다. 힙 내에서 특정 값을 가진 노드를 찾기 위해서는 모든 노드를 순회해야 한다. 이진 탐색이 안되는 이진트리지만, 힙은 한가지만은 확실하게 보장하고 있다 "힙에서 가장 작은 데이터를 갖는 노드는 루트 노드이다"
힙의 주요 연산은 노드 삽입, 루트 노드를 없애는 '최소값 삭제' 두 가지가 있다.
힙에 새 노드 삽입하기
힙의 삽입 연산은 세 단계를 거쳐 수행된다.
- 힙의 최고 깊이, 최 우측에 새 노드를 추가한다. 물론 이때 힙은 완전 이진 트리를 유지하도록 해야 한다.
- 삽입한 노드를 부모 노드와 비교한다. 삽입한 노드가 부모 노드보다 크면 제 위치에 삽입 된 것으로 연산을 종료한다. 하지만 부모 노드보다 작으면 다음 단계를 진행한다.
- 삽입한 노드가 부모 노드보다 작으면 부모 노드와 삽입한 노드의 위치를 서로 바꾼다. 바꾸고 나면 단계2를 다시 진행한다.
새 노드 7을 힙의 가장 깊은 곳에 추가한다. 이 때 완전 이진 트리가 무너지면 안되므로노드 37의 오른쪽 자식으로 추가한다. 그리고 7은 37보다 작으므로 이 두 노드를 교환한다.
7이 37과 교환되어 한 단계 위로 올라왔다. 또 다시 부모 노드와 비교를 수행하여 7이 8보다 작으므로 이번에도 교환을 수행한다.
7이 한단계 올라오고 나서 루트 노드밖에 남지 않았다. 루트 노드 2는 7보다 작으니 힙 순서 속성을 위반하지 않으므로 삽입이 완료된다.
힙의 최소값 삭제
루트 노드를 삭제한 후의 뒤처리 과정은 다음과 같다.
-
힙의 루트에 최고 깊이, 최 우측에 있던 노드를 루트 노드로 옮겨온다. 이때 힙의 순서 속성이 파괴된다. 이를 복원하기 위한 작업을 다음 단계에서부터 시작한다.
-
옮겨온 노드의 양쪽 자식을 비교하여 작은 쪽 자식과 위치 교환을 한다. 왜 작은 값과 교환할까?? 힙 순서 속성이 지켜지려면 부모 노드는 양쪽 자식보다 작은 값을 가져야 하기 때문이다.
-
옮겨온 노드가 더 이상 자식이 없는 잎 노드가 되거나 양쪽 자식보다 작은 값을 갖는 경우에는 삭제 연산을 종료한다. 그렇지않으면 단계2를 반복한다.
힙의 구현
힙은 완전 이진 트리이다. 완전 이진 트리는 배열로 구현하기에 아주 좋은 자료구조이다. 완전 이진 트리를 배열로 나타내는 방법은 다음과 같다.
- 깊이 0의 노드는 배열의 0번 요소에 저장한다.
- 깊이 1의 노드(모두 2개)는 배열의 1~2번 요소에 저장한다.
- 깊이 2의 노드(모두 4개)는 배열의 3~6번 요소에 저장한다.
- 깊이 n의 노드(2n개)는 배열의 2n-1 ~ 2n+1-2번 요소에 저장한다.
이 배열의 장점은 완전 이진 트리인 힙의 각 노드의 위치나 부모/자식 관계 등을 배열의 인덱스만으로 단번에 알아낼 수 있다는 것이다.
-
k번 인덱스에 위치한 노드의 양쪽 자식들의 위치한 인덱스
- 왼쪽 자식 노드 : 2k + 1
- 오른쪽 자식 노드 : 2k + 2
- k번 인덱스에 위치한 노드의 부모 노드가 위치한 인덱스 : (k-1)/2의 몫
-
힙의 자료구조 선언
typedef int ElementType;
typedef struct tagHeapNode
{
ElementType data;
}NODE;
typedef struct tagHeap
{
NODE* node;
int capacity;
int usedSize;
} HEAP;
-
힙의 삽입 구현
void HEAP_insert(HEAP* h, ElementType data)
{
int currentPos = h->usedSize;
int parentPos = HEAP_getParent(currentPos);
if( h->usedSize == u->capacity )
{
h->capacity *= 2;
h->node = (HEAP*)reaaloc(h->node, sizeof(HEAP) * h->capacity);
}
h->node[currentPos].data = data;
// 후속처리
while( currentPos > 0 &&
h->node[curretPos].data < h->node[parentPos].data )
{
HEAP_swapNode(h, currentPos, parentPos);
currentPos = parentPos;
parentPos = HEAP_getParent(currentPos);
}
h->usedSize++;
}
-
힙의 최소값 삭제 구현
void HEAP_deleteMin(HEAP* h, NODE* root)
{
int parentPos = 0;
int leftPos = 0;
int rightPos = 0;
// root에 최소값을 저장
memcpy(root, &h->node[0], sizeof(NODE));
memset(&h->node[0], 0, sizeof(NODE));
h->usedSize--;
// 힙의 첫번째 요소에 마지막 요소의 값 복사
HEAP_swapNode(h, 0, h->usedSize);
leftPos = HEAP_getLeftChild(0);
rightPos = leftPos + 1;
// 힙순서 속성을 만족할 때까지 자식 노드와 교환 반복
while(1)
{
int selectChild = 0;
if( leftPos >= h->usedSize )
break;
if( rightPos >= h->usedSize )
{
selectChild = leftPos;
}
else
{
if( h->node[leftPos].data > h->node[rightPos].data )
selectChild = rightPos;
else
selectChild = leftPos;
}
if( h->node[selectChild].data < h->node[parentPos].data )
{
HEAP_swapNode(h, parentPos, selectChild);
parentPos = selectChild;
}
else
break;
leftPos = HEAP_getLeftChild(parentPos);
rightPos = leftPos + 1;
}
if( h->usedSize < (h->capacity / 2) )
{
h->capacity /= 2;
h->node = (NODE*)realloc(h->node, sizeof(NODE) * h->capacity);
}
}
힙 예제 프로그램
- 예제 Heap.h
|
#ifndef _HEAP_H__ #define _HEAP_H__
#include <stdio.h> #include <memory.h> #include <stdlib.h>
typedef int ElementType; typedef struct tagHeapNode { ElementType data; }NODE;
typedef struct tagHeap { NODE* node; int capacity; int usedSize; }HEAP;
HEAP* HEAP_create(int initSize); void HEAP_destroy(HEAP* h); void HEAP_insert(HEAP* h, ElementType data); void HEAP_deleteMin(HEAP* h, NODE* root); int HEAP_getParent(int index); int HEAP_getLeftChild(int index); void HEAP_swapNode(HEAP* h, int index1, int index2); void HEAP_printNode(HEAP* h);
#endif |
- 예제 Heap.c
|
#include "Heap.h"
HEAP* HEAP_create(int initSize) { HEAP* newHeap = (HEAP*)malloc(sizeof(HEAP)); newHeap->capacity = initSize; newHeap->usedSize = 0; newHeap->node = (NODE*)malloc(sizeof(NODE) * newHeap->capacity);
printf("size : %d\n", sizeof(NODE));
return newHeap; } void HEAP_destroy(HEAP* h) { free(h->node); free(h); } void HEAP_insert(HEAP* h, ElementType data) { int currentPos = h->usedSize; int parentPos = HEAP_getParent(currentPos);
if( h->usedSize == h->capacity ) { h->capacity *= 2; h->node = (NODE*)realloc(h->node, sizeof(NODE) * h->capacity); }
h->node[currentPos].data = data;
// 후속처리 while( currentPos > 0 && h->node[currentPos].data < h->node[parentPos].data ) { HEAP_swapNode(h, currentPos, parentPos);
currentPos = parentPos; parentPos = HEAP_getParent(currentPos); }
h->usedSize++; } void HEAP_deleteMin(HEAP* h, NODE* root) { int parentPos = 0; int leftPos = 0; int rightPos = 0;
memcpy(root, &h->node[0], sizeof(NODE)); memset(&h->node[0], 0, sizeof(NODE));
h->usedSize--; HEAP_swapNode(h, 0, h->usedSize);
leftPos = HEAP_getLeftChild(0); rightPos = leftPos+1;
while(1) { int selectChild = 0;
if( leftPos >= h->usedSize ) break;
if( rightPos >= h->usedSize ) { selectChild = leftPos; } else { // 왼쪽 데이터가 크면 if(h->node[leftPos].data > h->node[rightPos].data) selectChild = rightPos; else selectChild = leftPos; }
// 선택된 데이터가 부모의 데이터보다 크면 if( h->node[selectChild].data < h->node[parentPos].data ) { HEAP_swapNode(h, parentPos, selectChild); parentPos = selectChild; } else break;
leftPos = HEAP_getLeftChild(parentPos); rightPos = leftPos + 1; }
// 메모리 재할당 if( h->usedSize < (h->capacity / 2) ) { h->capacity /= 2; h->node = (NODE*)realloc(h->node, sizeof(NODE) * h->capacity); } } int HEAP_getParent(int index) { return (int)((index-1) / 2); } int HEAP_getLeftChild(int index) { return (2 * index) + 1; } void HEAP_swapNode(HEAP* h, int index1, int index2) { int copySize = sizeof(NODE); NODE* temp = (NODE*)malloc(sizeof(NODE));
memcpy(temp, &h->node[index1], copySize); memcpy( &h->node[index1], &h->node[index2], copySize); memcpy( &h->node[index2], temp, copySize);
free(temp); } void HEAP_printNode(HEAP* h) { int i = 0; for( i = 0 ; i < h->usedSize ; i++ ) { printf("%d ", h->node[i].data); } printf("\n"); } |
- 예제 main.c
|
#include "Heap.h"
void main(void) { HEAP* h = HEAP_create(3); NODE minNode;
HEAP_insert(h, 12); HEAP_insert(h, 87); HEAP_insert(h, 111); HEAP_insert(h, 34); HEAP_insert(h, 17); HEAP_insert(h, 76); HEAP_printNode(h);
HEAP_deleteMin(h, &minNode); HEAP_printNode(h);
HEAP_deleteMin(h, &minNode); HEAP_printNode(h);
HEAP_deleteMin(h, &minNode); HEAP_printNode(h);
HEAP_deleteMin(h, &minNode); HEAP_printNode(h);
HEAP_deleteMin(h, &minNode); HEAP_printNode(h);
HEAP_deleteMin(h, &minNode); HEAP_printNode(h);
HEAP_destroy(h); } |
-
힙을 이용한 우선순위 큐의 구현
힙은 최소값(또는 최대값)을 즉시 얻어낼 수 있게 한다는 점에서 우선순위 큐를 구현하는데 아주 적격인 자료구조이다.
- 예제 PriorityQueue.h
|
#ifndef PRIORITYQUEUE_H_ #define PRIORITYQUEUE_H_
#include <stdio.h> #include <memory.h> #include <stdlib.h>
typedef int PriorityType;
typedef struct tagPQNode { PriorityType priority; void* data; }NODE;
typedef struct tagPriorityQueue { NODE* node; int capacity; int usedSize; }PQ;
PQ* PQ_create(int initSize); void PQ_destroy(PQ* pq); void PQ_enQueue(PQ* pq, NODE data); void PQ_deQueue(PQ* pq, NODE* root); int PQ_getParent(int idx); int PQ_getLeftChild(int idx); void PQ_swapNode(PQ* pq, int idx1, int idx2); int PQ_isEmpty(PQ* pq);
#endif |
- 예제 PriorityQueue.c
|
#include "PriorityQueue.h"
PQ* PQ_create(int initSize) { PQ* pq = (PQ*)malloc(sizeof(PQ)); pq->capacity = initSize; pq->usedSize = 0; pq->node = (NODE*)malloc(sizeof(NODE)* pq->capacity);
return pq; } void PQ_destroy(PQ* pq) { free(pq->node); free(pq); } void PQ_enQueue(PQ* pq, NODE data) { int currentPos = pq->usedSize; int parentPos = PQ_getParent(currentPos);
// 남아있는 공간이 없으면 if( pq->usedSize == pq->capacity ) { if( pq->capacity == 0 ) { pq->capacity = 1; }
pq->capacity *= 2; pq->node = (NODE*)realloc(pq->node, sizeof(NODE) * pq->capacity); }
pq->node[currentPos] = data;
// 후속처리 // 현재 위치가 0보다 크고 // 현재 위치의 우선순위가 부모 우선순위보다 높으면 while( currentPos > 0 && pq->node[currentPos].priority < pq->node[parentPos].priority) { PQ_swapNode(pq, currentPos, parentPos);
currentPos = parentPos; parentPos = PQ_getParent(currentPos); }
// pq->usedSize++;
} void PQ_deQueue(PQ* pq, NODE* root) { int parentPos = 0; int leftPos = 0; int rightPos = 0;
memcpy(root, &pq->node[0], sizeof(NODE)); memset(&pq->node[0], 0, sizeof(NODE));
pq->usedSize--; PQ_swapNode(pq, 0, pq->usedSize);
leftPos = PQ_getLeftChild(0); rightPos = leftPos+1;
while(1) { int selectChild = 0;
if( leftPos >= pq->usedSize ) break;
if( rightPos >= pq->usedSize ) { selectChild = leftPos; } else { if( pq->node[leftPos].priority > pq->node[rightPos].priority ) selectChild = rightPos; else selectChild = leftPos; }
if( pq->node[selectChild].priority < pq->node[parentPos].priority ) { PQ_swapNode(pq, parentPos, selectChild); parentPos = selectChild; } else { break; }
leftPos = PQ_getLeftChild(parentPos); rightPos = leftPos+1; }
if( pq->usedSize < (pq->capacity / 2) ) { pq->capacity /= 2; pq->node = (NODE*)realloc(pq->node, sizeof(NODE) * pq->capacity); } } int PQ_getParent(int idx) { return (int)((idx-1) / 2); } int PQ_getLeftChild(int idx) { return (2 * idx) + 1; } void PQ_swapNode(PQ* pq, int idx1, int idx2) { int copySize = sizeof(NODE); NODE* temp = (NODE*)malloc(copySize);
memcpy( temp, &pq->node[idx1], copySize); memcpy( &pq->node[idx1], &pq->node[idx2], copySize); memcpy( &pq->node[idx2], temp, copySize);
free(temp); } int PQ_isEmpty(PQ* pq) { return ( pq->usedSize == 0 ); } |
- 예제 main.c
|
#include "PriorityQueue.h"
void printNode(NODE* node) { printf("작업명 : %s (우선순위:%d)\n", node->data, node->priority); }
void main() { PQ* pq = PQ_create(3); NODE pop;
NODE node[7] = { {32, (void*)"코딩"}, {12, (void*)"롤"}, {87, (void*)"운동"}, {45, (void*)"게임"}, {35, (void*)"문서작업"}, {66, (void*)"디버깅"}, };
for( int i = 0 ; i < 6 ; i++ ) { PQ_enQueue(pq, node[i]); }
printf("큐에 남아있는 작업 수 : %d\n", pq->usedSize);
while( !PQ_isEmpty(pq) ) { PQ_deQueue(pq, &pop); printNode(&pop); }
PQ_destroy(pq); } |