heap은 완전 이진 tree를 이용하여 heap에 값을 넣을 때나 뽑을 때 항상 최대 또는 최소 값을 정렬하여 저장하도록 구성됩니다.
완전 이진 tree의 부모는 자식보다 클 때 root가 최대값을 가지는 최대 heap을
부모가 자식보다 작을 때 최소값을 가지는 최소 heap을 구현할 수 있습니다.
1) 삽입 방법 - 배열의 끝에 추가한 후 부모와 자식의 관계를 이용하여 위로 재 정렬 합니다.
2) 추출 방법 - 루트를 추출하여 사용한 후 배열의 끝 원소를 root 자리로 옮긴 다음 아래로 정렬 합니다.
좌우 tree가 균형적일 경우에는 배열로 표현하는 것이 유리합니다.
장점 - list로 구현할 때 소비되는 연결 pointer에 대한 memory 공간을 절약할 수 있고
pointer 연산에 필요한 memory 접근을 수식 연산으로 대체합니다.
memory 접근 비용보다 수식 연산이 빠릅니다.
단점 - 배열 크기를 사전에 결정하여 할당해야 하기 때문에 구현 시 배열 크기가 가늠이 되지 않을 경우에는 사용이 어렵고 사전에 결정이 가능하다고 하더라도 시작부터 전체 메모리를 할당하고 시작해야 하기 때문에 메모리를 효율적으로 사용하기 어렵습니다.
| 왼쪽 자식 index 계산식 | (2 x 부모 index) + 1 |
| 오른쪽 자식 index 계산식 | 왼쪽 자식 inex + 1 |
| 부모 index 계산식 | (자식 index - 1) / 2 |
#define MAX_SIZE 100
int heap[MAX_SIZE];
int heapSize = 0;
void heapInit(void)
{
heapSize = 0;
}단순하게 100개 원소를 가지는 배열에 heap을 구현해 보겠습니다.
위에서 부모와 자식의 index를 계산하는 표를 구현해 보면 아래와 같습니다.
| 왼쪽 자식 index 계산식 | (2 x 부모 index) + 1 | int leftChild(int parent) { return (parent * 2) + 1; } |
| 오른쪽 자식 index 계산식 | 왼쪽 자식 inex + 1 | int rightChild(int parent) { return leftChild(parent) + 1; } |
| 부모 index 계산식 | (자식 index - 1) / 2 | int parent(int child) { return (child - 1) / 2; } |
최대 heap 과 최소 heap을 모두 지원하기 위해서 전역변수로 정의하고 그에 따라 비교 결과를 반환 하였습니다.
bool g_max_heap = true;
int compare(int child, int parent)
{
if (g_max_heap) {
if (heap[child] > heap[parent]) return 1;
return 0;
}
else {
if (heap[child] < heap[parent]) return 1;
return 0;
}
}이들을 이용하여 삽입 함수는 아래와 같이 구현 하였습니다.
int heapPush(int value)
{
if (heapSize + 1 > MAX_SIZE) {
printf("queue is full!");
return 0;
}
int current = heapSize;
heapSize++;
heap[current] = value;
while (current > 0 && compare(current, parent(current))) {
swap(current, parent(current));
current = parent(current);
}
return current;
}추출 함수는 아래와 같이 구현 하였습니다.
int heapPop(int *value)
{
if (heapSize <= 0) {
return -1;
}
*value = heap[0];
heap[0] = heap[heapSize - 1];
heapSize--;
int current = 0;
while (leftChild(current) < heapSize) {
int child;
if (rightChild(current) >= heapSize) child = leftChild(current); // There is only leftChild.
else if (compare(leftChild(current), rightChild(current))) child = leftChild(current);
else child = rightChild(current);
if (compare(child, current)) {
swap(child, current);
current = child;
}
else break;
}
return current;
}이 함수들은 아래와 같이 사용할 수 있겠습니다.
int main(void)
{
int data[] = { 10, 5, 8, 7, 2, 4, 1 };
int len = sizeof(data) / sizeof(data[0]);
heapInit();
for (int i = 0; i < len; i++) {
heapPush(data[i]);
}
for (int i = 0; i < len; i++) {
int value;
heapPop(&value);
printf("%d ", value);
}
}우선 순위 queue
각 원소가 우선 순위를 가지고 있을 때 queue에서 최소 또는 최대 우선 순위의 원소를 추출하는 기능을 가지고 있는 자료 구조를 우선 순위 queue라고 합니다.
우선 순위 queue는 heap을 이용하여 구현하는 것이 일반적이며 우선 순위 기능을 구현하기 용이한 다른 자료 구조로 구현 할 수도 있습니다.
댓글