티스토리 뷰
주의 사항!
- 이 글은 제가 직접 공부하는 중에 작성되고 있습니다.
- 따라서 제가 이해하는 그대로의 내용이 포함됩니다.
- 따라서 이 글은 사실과는 다른 내용이 포함될 수 있습니다.
힙의 구현을 위해서는 데이터의 저장과 삭제의 방법을 먼저 알아야 합니다. 따라서 먼저 데이터의 저장 과정을 '최소 힙'을 기준으로 설명하겠습니다.
위 힙의 데이터가 데이터이자 곧 우선순위라고 가정하겠습니다. 여기에 2를 저장하는 알고리즘을 어떻게 구성할 수 있을까요? 책에서 소개하는 알고리즘은 다음과 같습니다.
- 우선 우선순위가 가장 낮다고 가정하고 힙의 마지막 위치에 저장합니다.
- 마지막 위치란 마지막 레벨의 가장 오른쪽 노드 자리를 말합니다. 만약 마지막 레벨이 다 채워지면 그 다음 레벨의 가장 왼쪽 노드 자리를 마지막 위치로 합니다.
- 새로 저장한 데이터의 우선순위를, 부모의 데이터의 우선순위와 비교합니다.
- 우선순위를 비교해서 새로 추가한 데이터의 우선순위가 부모의 것보다 더 높으면 부모와 노드 자리를 바꿉니다.
- 더 이상 바꿀 수 없을 때까지 부모와 우선순위를 비교하고 자리를 바꾸는 알고리즘을 반복합니다.
이 알고리즘을 그림으로 설명해 보겠습니다.
힙의 마지막 위치에 새로운 노드 2가 추가되었습니다. 그리고 이 노드와 부모 노드의 우선순위를 비교합니다.
우선순위를 비교하여 2와 12의 위치가 바뀌었습니다. 다시 부모 노드인 4와 우선순위를 비교합니다.
우선순위를 비교하여 2와 4의 위치가 바뀌었습니다. 다시 부모 노드인 1과 우선순위를 비교합니다.
1과 2의 우선순위를 비교하면 2의 우선순위가 1보다 낮으므로 위치를 바꾸지 않고 알고리즘을 종료합니다.
이제 삭제 과정을 설명하겠습니다. 힙의 경우 우선순위가 가장 높은 데이터가 먼저 꺼내지기 때문에 반드시 루트 노드를 삭제하게 됩니다. 따라서 위의 힙에서 1을 삭제한다고 가정해 보겠습니다. 삭제 알고리즘은 다음과 같습니다.
- 루트 노드를 삭제한다.
- 힙의 가장 마지막 위치에 있는 노드를 루트 노드로 옮긴다.
- 옮긴 후, 자식 노드 중 우선순위가 높은 노드와 우선순위를 비교한다.
- 자식 노드보다 우선순위가 낮으면 해당 자식 노드와 자리를 바꾼다.
- 자리를 더 바꿀 수 없을 때까지 우선순위가 높은 자식 노드와 비교하고 자리를 바꾼다.
위 알고리즘을 그림으로 표현하면 다음과 같습니다.
먼저, 루트 노드를 삭제했습니다.
가장 마지막 위치에 있던 노드를 루트 노드로 옮겼습니다. 그리고 자식 노드인 2와 8중에 우선순위가 더 높은 2와 우선순위를 비교합니다.
2의 우선순위가 12보다 높기 때문에 2와 12의 자리를 바꾸었습니다. 그리고 이번에는 자식 노드인 4와 9중에 우선순위가 더 높은 4와 우선순위를 비교합니다.
4의 우선순위가 더 높으므로 자리를 바꾸었습니다. 이번에는 자식 노드인 18과 우선순위를 비교합니다.
12의 우선순위가 더 높으므로 자리를 바꾸지 않고 알고리즘을 종료합니다.
이제 힙의 저장과 삭제 과정을 알아봤으므로 힙을 직접 구현해 볼 차례입니다. 힙은 기본적으로 이진 트리이기 때문에 우리는 트리를 구현해야 합니다. 이전까지 트리는 연결 리스트를 기반으로 구현했기 때문에 힙 또한 연결 리스트를 기반으로 구현하는 것이 좋아 보입니다. 분명 트리를 구현하기에는 연결 리스트가 더 유리합니다. 하지만 힙의 경우는 다릅니다. 힙은 연결 리스트가 아닌 배열을 기반으로 구현하는 것이 원칙으로 여겨지고 있습니다.
힙은 '마지막 위치'라고 하는 것을 구해야 합니다. 마지막 위치는 트리의 마지막 레벨의 가장 오른쪽에 위치한 노드를 의미합니다. 연결 리스트를 기반으로 구현한 트리에서 마지막 위치를 어떻게 구할 수 있을지 알고리즘을 한 번 고민해보기 바랍니다. 대충 생각해 봐도 루트 노드를 시작으로 좌우 자식 노드에 하나하나 접근해가며 찾는 방법밖에는 떠오르질 않습니다.
연결 리스트 기반의 트리에서 '마지막 위치'를 찾을 수 없는 것은 아닙니다. 다만 그 위치를 찾기 위한 알고리즘이 비효율적이고 구현하기 힘듧니다. 아래의 힙을 배열 기반으로 구현하면 다음과 같은 형태를 가집니다.
그리고 배열로 표현하면 다음과 같이 됩니다.
| 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 |
| 2 | 4 | 8 | 12 | 9 | 15 | 21 | 18 |
배열의 1번지부터 시작해서 각각의 번지수에 맞게 힙에도 번호가 새겨져 있습니다. 때문에 배열 기반의 힙에서는 배열의 마지막 요소의 번지수를 활용해서 힙의 마지막 위치를 찾을 수 있습니다. 그리고 한 노드의 번호를 통해 자식 노드의 번호도 계산할 수 있습니다. 왼쪽 자식 노드의 번호는 부모 노드의 번호에 2를 곱한 것과 같고 오른쪽 자식 노드는 이에 1을 더한 것과 같습니다.
이제 배열 기반의 힙을 구현해 보겠습니다. 우선은 좋은 모델은 아니지만 이해하기 용이한 방식으로 힙을 구현해 보고자 합니다. 그리고 이어서 이보다 더 합리적인 형태로 변경하기로 하겠습니다. 이제 힙의 구현을 위한 헤더 파일을 다음과 같이 정의합니다.
//ArrayListBasedHeap.h 헤더 파일로 저장
#ifndef ARRAYLISTBASEDHEAP
#define ARRAYLISTBASEDHEAP
#define TRUE 1
#define FALSE 0
#define HEAP_LEN 100
typedef char HData;
typedef int Priority;
typedef struct HeapElem
{
Priority pr;
HData data;
}HeapElem;
typedef struct Heap
{
int numOfData;
HeapElem heapArr[HEAP_LEN];
} Heap;
void HeapInit(Heap* ph);
int HIsEmpty(Heap* ph);
void HInsert(Heap* ph, HData data, Priority pr);
HData HDelete(Heap* ph);
#endif위 코드에서 다음과 같이 정의된 구조체를 보면,
typedef struct HeapElem
{
Priority pr; //값이 작을수록 더 높은 우선순위
HData data;
}HeapElem;데이터뿐만 아니라 우선순위 정보까지 저장하고 있음을 알 수 있습니다. 위 헤더 파일은 우선순위 큐의 구현을 고려하여 정의되었기 때문에 힙에 저장되는 HeapElem는 데이터와 우선순위 정보를 같이 가지고 있습니다. HeapElem는 트리의 노드와 같습니다.
이제 위에서 정의한 헤더 파일을 기반으로 각 함수들을 정의해 보겠습니다. 그런데 함수들을 정의하기에 앞서 다음의 사실들을 정리하고 기억할 필요가 있습니다.
- 힙은 완전 이진 트리입니다.
- 힙의 구현은 배열을 기반으로 하며 인덱스가 0인 요소는 비워둔다.
- 따라서 힙에 저장된 노드의 개수와 마지막 노드의 고유번호는 같습니다.
- 노드의 고유번호가 노드가 저장되는 배열의 인덱스 값이 됩니다.
- 우선순위를 나타내는 정수 값이 작을수록 높은 우선순위를 나타낸다고 가정합니다.
위 사실들을 주의하여 각 함수들을 정의해 봅니다. 아래에 소개되는 함수의 정의들을 보기 전에 직접 한 번 정의해 보는 것을 권합니다. 다음은 제가 직접 정의한 함수들입니다.
//ArrayListBaseHeap.c 소스 파일로 저장
#include "ArrayListBasedHeap.h"
#include <stdio.h>
void HeapInit(Heap* ph)
{
ph->numOfData = 0;
}
int HIsEmpty(Heap* ph)
{
return (ph->numOfData == 0) ? TRUE : FALSE;
}
int PriorityFunc(int pr1, int pr2) //첫 번째 인자의 값이 두 번째 인자보다 작으면 참 반환
{
return (pr1 < pr2) ? TRUE : FALSE;
}
void HInsert(Heap* ph, HData data, Priority pr)
{
HeapElem elem = { pr, data };
ph->numOfData++;
int index = ph->numOfData;
int parentIndex = index / 2;
while (parentIndex >= 1 && PriorityFunc(elem.pr, ph->heapArr[parentIndex].pr))
{
ph->heapArr[index] = ph->heapArr[parentIndex];
index = parentIndex;
parentIndex = index / 2;
}
ph->heapArr[index] = elem;
}
int GetChildIndex(Heap* ph, int parentIdx, int* pidx) //자식이 존재하면 참 반환, 좌우 자식 중 우선순위가 높은 자식 인덱스를 pidx에 저장
{
if (parentIdx * 2 > ph->numOfData)
{
return FALSE;
}
int leftChildIdx = parentIdx * 2;
int rightChildIdx = leftChildIdx + 1;
if (rightChildIdx > ph->numOfData)
{
*pidx = leftChildIdx;
return TRUE;
}
*pidx = (PriorityFunc(ph->heapArr[leftChildIdx].pr, ph->heapArr[rightChildIdx].pr)) ? leftChildIdx : rightChildIdx;
return TRUE;
}
HData HDelete(Heap* ph)
{
HeapElem elem = ph->heapArr[ph->numOfData--];
HData data = ph->heapArr[1].data;
int index = 1;
int childIndex;
while (GetChildIndex(ph, index, &childIndex) && PriorityFunc(ph->heapArr[childIndex].pr, elem.pr))
{
ph->heapArr[index] = ph->heapArr[childIndex];
index = childIndex;
}
ph->heapArr[index] = elem;
return data;
}헤더 파일에 정의된 함수 외에 두 개의 함수들이 추가로 정의되었습니다.
int PriorityFunc(int pr1, int pr2) //첫 번째 인자의 값이 두 번째 인자보다 작으면 참 반환
{
return (pr1 < pr2) ? TRUE : FALSE;
}위 함수는 우선순위를 비교하는 함수입니다. 나중에 우선순위 판단 기준이 바뀔 것을 고려하여 위 함수를 만들어 보았습니다.
int GetChildIndex(Heap* ph, int parentIdx, int* pidx) //자식이 존재하면 참 반환, 좌우 자식 중 우선순위가 높은 자식 인덱스를 pidx에 저장
{
if (parentIdx * 2 > ph->numOfData)
{
return FALSE;
}
int leftChildIdx = parentIdx * 2;
int rightChildIdx = leftChildIdx + 1;
if (rightChildIdx > ph->numOfData)
{
*pidx = leftChildIdx;
return TRUE;
}
*pidx = (PriorityFunc(ph->heapArr[leftChildIdx].pr, ph->heapArr[rightChildIdx].pr)) ? leftChildIdx : rightChildIdx;
return TRUE;
}위 함수는 입력받은 parentIdx를 가지고 자식 노드가 있는지 없는지 판단합니다. 자식 노드가 하나도 없으면 FALSE를 반환하고 하나라도 있으면 TRUE를 반환합니다. 그리고 자식 중 우선수위가 더 높은 자식의 index를 pidx에 저장합니다.
구현이 끝난 힙을 테스트하기 위해 main 함수를 다음과 같이 정의하고 그 실행결과를 확인합니다.
//main.c 소스 파일로 저장
#include <stdio.h>
#include "ArrayListBasedHeap.h"
int main(void)
{
Heap heap;
HeapInit(&heap);
HInsert(&heap, 'A', 1);
HInsert(&heap, 'B', 2);
HInsert(&heap, 'C', 3);
printf("%c \n", HDelete(&heap));
HInsert(&heap, 'A', 1);
HInsert(&heap, 'B', 2);
HInsert(&heap, 'C', 3);
printf("%c \n", HDelete(&heap));
while (!HIsEmpty(&heap))
{
printf("%c \n", HDelete(&heap));
}
return 0;
}
/*
실행결과
A
A
B
B
C
C
*/위 실행결과를 보면 힙의 구현이 제대로 이루어졌음을 확인할 수 있습니다. 하지만 이렇게 정의한 힙을 이용해서 우선순위 큐를 구현하는 것에는 무리가 있습니다. 왜냐하면 앞서 구현한 힙은 데이터의 우선순위를 직접 알려줘야 했기 때문입니다. 우선순위 큐는 우선순위를 별도로 알려주지 않아도 입력받은 데이터를 바탕으로 직접 우선 선위를 판단할 수 있어야 합니다.
우선순위 큐를 구현하기 위해서는 힙에 우선순위 판단 기준을 설정할 수 있어야 합니다. 그래서 위에서 구현했던 힙을 수정할 것입니다. 앞서 구현했던 힙은 다음의 구조체를 가지고 있었습니다.
typedef char HData;
typedef int Priority;
typedef struct HeapElem
{
Priority pr;
HData data;
}HeapElem;
typedef struct Heap
{
int numOfData;
HeapElem heapArr[HEAP_LEN];
} Heap;이 구조체를 다음과 같이 변경합니다.
typedef char HData;
typedef int(*PriorityComp)(HData d1, HData d2);
typedef struct Heap
{
PriorityComp comp;
int numOfData;
HData heapArr[HEAP_LEN];
} Heap;우선 HeapElem 구조체가 사라졌습니다. 그리고 Heap 구조체의 HeapElem을 저장하던 배열이 HData를 저장하는 배열로 바뀌었습니다. 그리고 함수 포인터 PriorityComp가 생겼습니다. 이 함수 포인터가 가리킬 함수는 데이터 두 개를 받아 우선순위를 결정짓는 일을 수행합니다. 해당 함수를 어떻게 정의할지는 프로그래머의 결정에 따라 달라집니다. 이 함수의 주요 역할은 다음과 같습니다.
- 첫 번째 인자의 우선순위가 두 번째 인자의 우선순위보다 높으면 1 반환
- 첫 번째 인자의 우선순위와 두 번째 인자의 우선순위가 같으면 0 반환
- 첫 번째 인자의 우선순위가 두 번째 인자의 우선순위보다 낮으면 -1 반환
Heap 구조체의 구조가 바뀌었으므로 몇 함수들의 변경도 불가피합니다. 위 구조체에 맞게 변경이 필요한 함수들을 적절히 변경해 봅니다.
우선 변경된 헤더 파일입니다.
//ArrayListBasedHeap.h 헤더 파일로 저장
#ifndef ARRAYLISTBASEDHEAP
#define ARRAYLISTBASEDHEAP
#define TRUE 1
#define FALSE 0
#define HEAP_LEN 100
typedef char HData;
typedef int(*PriorityComp)(HData d1, HData d2);
typedef struct Heap
{
PriorityComp comp;
int numOfData;
HData heapArr[HEAP_LEN];
} Heap;
void HeapInit(Heap* ph, PriorityComp comp);
int HIsEmpty(Heap* ph);
void HInsert(Heap* ph, HData data);
HData HDelete(Heap* ph);
#endif그리고 다음은 변경된 함수들의 구현입니다.
//ArrayListBaseHeap.c 소스 파일로 저장
#include "ArrayListBasedHeap.h"
#include <stdio.h>
void HeapInit(Heap* ph, PriorityComp comp)
{
ph->numOfData = 0;
ph->comp = comp;
}
int HIsEmpty(Heap* ph)
{
return (ph->numOfData == 0) ? TRUE : FALSE;
}
void HInsert(Heap* ph, HData data)
{
ph->numOfData++;
int index = ph->numOfData;
int parentIndex = index / 2;
while (parentIndex >= 1 && ph->comp(data, ph->heapArr[parentIndex]) > 0)
{
ph->heapArr[index] = ph->heapArr[parentIndex];
index = parentIndex;
parentIndex = index / 2;
}
ph->heapArr[index] = data;
}
int GetChildIndex(Heap* ph, int parentIdx, int* pidx) //자식이 존재하면 참 반환, 좌우 자식 중 우선순위가 높은 자식 인덱스를 pidx에 저장
{
int leftChildIdx = parentIdx * 2;
if (leftChildIdx > ph->numOfData)
{
return FALSE;
}
int rightChildIdx = leftChildIdx + 1;
if (rightChildIdx > ph->numOfData)
{
*pidx = leftChildIdx;
return TRUE;
}
*pidx = (ph->comp(ph->heapArr[leftChildIdx], ph->heapArr[rightChildIdx]) > 0) ? leftChildIdx : rightChildIdx;
return TRUE;
}
HData HDelete(Heap* ph)
{
HData delData = ph->heapArr[1];
HData lastData = ph->heapArr[ph->numOfData--];
int index = 1;
int childIndex;
while (GetChildIndex(ph, index, &childIndex) && ph->comp(ph->heapArr[childIndex], lastData) > 0)
{
ph->heapArr[index] = ph->heapArr[childIndex];
index = childIndex;
}
ph->heapArr[index] = lastData;
return delData;
}위 코드를 보면,
void HeapInit(Heap* ph, PriorityComp comp)
{
ph->numOfData = 0;
ph->comp = comp;
}위 함수는 힙을 초기화하는 함수인데 초기화 과정에서 우선순위를 판단하는 함수를 전달받도록 변경되었습니다.
void HInsert(Heap* ph, HData data)
{
ph->numOfData++;
int index = ph->numOfData;
int parentIndex = index / 2;
while (parentIndex >= 1 && ph->comp(data, ph->heapArr[parentIndex]) > 0)
{
ph->heapArr[index] = ph->heapArr[parentIndex];
index = parentIndex;
parentIndex = index / 2;
}
ph->heapArr[index] = data;
}위 함수의 경우 우선순위 정보까지 전달받았었지만 지금은 우선순위 정보는 전달받지 않습니다. 그리고 우선순위를 판단하기 위해 힙의 comp가 가리키는 함수를 호출하는 모습입니다.
나머지 함수들에서도 우선순위를 판단하는 comp를 호출하는 것으로 변경되었을 뿐 크게 변경된 부분은 없습니다. 그런데 함수들을 구현한 소스 파일에 보면 우선순위를 판단하는 함수는 정의되지 않았습니다. 해당 함수는 프로그래머가 이 힙을 사용할 때, 프로그래머가 직접 작성해서 사용할 함수이기 때문에 위 소스파일에는 정의되어 있지 않습니다.
이제 이렇게 구현된 힙을 테스트하기 위해 다음과 같이 main 함수를 정의하고 그 실행결과를 확인해 보겠습니다.
//main.c 소스 파일로 저장
#include <stdio.h>
#include "ArrayListBasedHeap.h"
int PriorityComparision(char ch1, char ch2)
{
if (ch1 == ch2)
{
return 0;
}
else
{
return (ch1 < ch2) ? 1 : -1;
}
}
int main(void)
{
Heap heap;
HeapInit(&heap, PriorityComparision);
HInsert(&heap, 'A');
HInsert(&heap, 'B');
HInsert(&heap, 'C');
printf("%c \n", HDelete(&heap));
HInsert(&heap, 'A');
HInsert(&heap, 'B');
HInsert(&heap, 'C');
printf("%c \n", HDelete(&heap));
while (!HIsEmpty(&heap))
{
printf("%c \n", HDelete(&heap));
}
return 0;
}
/*
실행결과
A
A
B
B
C
C
*/이렇게 힙의 구현이 끝이 났습니다.
사실 위와 같이 구현한 힙은 우선순위 큐와 같습니다. 우리는 힙을 구현하고 있었지만 결과적으로 우선순위 큐를 구현해냈습니다. 그도 그럴 것이 힙에 우선순위를 판단하는 기능만 추가하면 우선순위 큐가 되기 때문입니다.
'공부 일지 > 자료구조 공부 일지' 카테고리의 다른 글
| Chapter 10. 복잡하지만 효율적인 정렬 알고리즘 (0) | 2021.03.20 |
|---|---|
| Chapter 10. 단순한 정렬 알고리즘 (3) | 2021.03.18 |
| Chapter 09. 우선순위 큐의 이해 (0) | 2021.03.18 |
| Chapter 08. 수식 트리(Expression Tree)의 구현 (2) (0) | 2021.03.18 |
| Chapter 08. 수식 트리(Expression Tree)의 구현 (0) | 2021.03.17 |