저번에 했던 heap의 나머지 이야기를 해보자.
우선순위를 알아서 따지는 heap 구현
저번 09-1에서 이런 이야기를 했었다.
어? 근데 우선순위를 굳이 내가 집어넣어야하나? 그럼 너무 귀찮은거 아닌가요? 컴퓨터가 알아서 해주는줄..
이에 대해 이렇게 답했다.
일단 Heap 자체를 구현하고 이해하기 위해 코드를 이렇게 짰는데, 이제 코드에서 우선순위를 알아서 매겨주는 구조는 저자가 이 코드를 다 짜본 후에 알려주겠다고 했다. 기다리자.
여기서 말한, "우선순위를 알아서 매겨주는 구조의 코드"를 지금 짜보도록 하겠다.
데이터를 3200개를 넣는다고 가정했을 때, 3200개의 우선순위를 일일히 우리가 "직접" 따져봐서, 각 데이터별로 "직접" 넣어주기는, 너무 숫자가 많지 않은가.
그래서, 여기에 우선순위를 "컴퓨터가 알아서" 따져주는 과정을 삽입하려고 한다.
그러면, 기존에 우리가 짰던 heap에서 무엇을 바꿔야 할까?
컴퓨터가 우선순위를 "알아서" 따지려면, 우선순위를 따지는 그 "기준" 을 우리가 넣어줘야한다. 기준까지 얘네가 알아서 따지는건, 무슨 인공지능 프로그램을 만드는게 아니지 않는가?
그 우선순위의 판단 기준을 우리가 넣어주려면, 헤더파일부터 건드려야 한다.
앞에서, 힙의 구현을 위해 필요한 구조체를 두개를 정의했었다.
typedef struct _heapElem {
Priority pr;
HData data;
} HeapElem;
typedef struct _heap {
int numOfData;
HData heapArr[HEAP_LEN];
} Heap;근데, 우선순위를 알아서 따진다면 "힙에 저장될 데이터의 모델"을 뜻하는 heapElem 은 굳이 필요가 없을거다.
HeapElem을 굳이 만들어준 이유는, "데이터와 우선순위를 하나로 묶기 위한 것" 이였는데, 우선순위를 저장하는 멤버는 아예 없애버리니, HData data 하나만 굳이 구조체에 넣을바에 아래에 합쳐주는게 낫지 않겠는가..
typedef struct _heap {
PriorityComp *comp; // typedef int (*PriorityComp) (HData d1, HData d2);
int numOfData;
HData heapArr[HEAP_LEN];
}
이렇게 해주면 되지 않을까.
PriorityComp *comp 가 아까 우리가 말한 "우선순위를 따지는 기준" 이다.
함수 포인터 변수를 통해서 데이터 d1, d2를 대상으로 우선순위의 높고 낮음을 판단하게 할 수 있다.
이 comp 함수 정의를 위한 GuideLine은 저자가 set한 기준으로 작성하겠다.
1. 첫번째 인자의 우선 순위가 높다면 양수 반환
2. 두번째 인자의 우선 순위가 높다면 음수 반환
2. 두 인자의 우선 순위가 동일하다면 0 반환
아마 이렇게 구조체를 바꿔준다면, 기존에 구현했던 함수 중 일부는 좀 바뀌는 부분이 있을 것이다.
-
HeapInit 에서 초기화를 진행할 때 ph->comp (판단기준)을 인자로 받아서 넣어줘야 할 것이다.
-
HInsert에서 우선순위 비교를 comp를 통해 진행해야하니 if문들이 바뀔 것이다.
-
HDelete, 위의 HInsert와 마찬가지.
-
GetHIChildIDX, 위의 HInsert와 마찬가지.
한번, 헤더파일부터 구현해보자.
/* RealHeap.h */
#ifndef __REAL_HEAP_H__
#define __REAL_HEAP_H__
#define TRUE 1
#define FALSE 0
#define HEAP_LEN 100
typedef char HData;
typedef int (*PriorityComp) (HData d1, HData d2);
// PriorityComp 함수 포인터의 typedef 선언
typedef struct _heap {
PriorityComp pc; // 우선순위 비교기준
int numOfData = 0;
HData heapArr[HEAP_LEN];
} Heap;
void HeapInit(Heap *ph, PriorityComp pc);
int HIsEmpty(Heap *ph);
void HInsert(Heap *ph, HData data);
HData HDelete(Heap *ph);
#endif아래 코드에선 Ch.09-1에 있는 "SimpleHeap.c"와 같은 부분은
... 09-1의 SimpleHeap.c와 동일 ...
이라고 표기했다.
그리고, 기존과 차이가 있는 부분은
// 차이가 있는 부분
이라는 주석이 있을 것이다. 참고하자.
/* RealHeap.c */
#include "RealHeap.h"
void HeapInit(Heap *ph, PriorityComp pc) {
ph->numOfData = 0;
ph->comp = pc;
}
int HIsEmpty(Heap *ph) {
... 09-1의 SimpleHeap.c와 동일 ...
}
int GetParentIDX (int idx) {
... 09-1의 SimpleHeap.c와 동일 ...
}
int GetLChildIDX (int idx) {
... 09-1의 SimpleHeap.c와 동일 ...
}
int GetRChildIDX (int idx) {
... 09-1의 SimpleHeap.c와 동일 ...
}
int GetHIChildIDX (Heap *ph, int idx) {
if (GetLChildIDX(idx) > ph->numOfData) {
return 0;
} else if (GetLChildIDX(idx) == ph->numOfData) {
return GetLChildIDX(idx);
} else { // 차이가 있는 부분
if (ph->comp(ph->heapArr[GetLChildIDX(idx)], ph->heapArr[GetRChildIDX(idx)] < 0) {
return GetRChildIDX(idx);
} else {
return GetLChildIDX(idx);
}
}
}
void HInsert(Heap *ph, HData data) {
int idx = ph->numOfData+1;
while (idx != 1) {
// 차이가 있는 부분
if (ph->comp(data, ph->heapArr[GetParentIDX(idx)]) > 0) {
ph->heapArr[idx] = ph->heapArr[GetParentIDX(idx)];
idx = GetParentIDX(idx);
} else {
break;
}
}
ph-heapArr[idx] = data;
ph->numOfData += 1;
}
HData HDelete(Heap *ph) {
HData rdata = ph->heapArr[1];
HData lastElem = ph->heapArr[ph->numOfData];
int parentIdx = 1;
int childIdx;
while (childIdx = GetHIChildIDX(ph, parentIdx)) {
// 차이가 있는 부분
if(ph->comp(lastElem, ph->heapArr[childIdx]) >= 0) {
break;
}
ph->heapArr[parentIdx] = ph->heapArr[childIdx];
parentIdx = childIdx;
}
ph->heapArr[parentIdx] = lastElem;
ph->numOfData -= 1;
return rdata;
}이렇게, 우리가 우선순위 큐를 처음 짜려고 할때, 우리가 원했던 코드들이 짜졌다.
그런데, 하나 부족하다고 생각하지 않나..?
계속 보면 ph->comp 와 같은 우선순위 비교연산을 진행하고 있는데, 여기서 이 비교기준을 나타내는 함수는 어딨는가?
지금 위에 작성한 코드들에선 없다!
이 비교기준은 메인함수에서 따로 작성해주면 된다.
/* RealHeapMain.c */
int DataPriorityComp (char d1, char d2) { // 알파벳이 data라 가정
return d2-d1;
}
// 아스키코드로 연산하여 정수값을 반환한다.
// 만약 d1='A', d2='B' 라면 B-A 는 양수. 즉 A(d1)가 우선순위가 더 높다.
int main() {
.
.
.
}그리고 우선순위 큐 챕터"에 포함된" Heap을 지금까지 공부한건데..
솔직히 우선순위 큐나 Heap이나 다른게 없어보인다. HInsert가 enqueue이고, HDelete가 dequeue, HeapInit이 PQueueInit..
그래서 ADT를 대충 정의는 해주지만, 정말 큰 차이가 없다는것만 알아두자.
/* PriorityQueue.h */
#ifndef __PRIORITY_QUEUE_H__
#define __PRIORITY_QUEUE_H__
#include "RealHeap.h"
typedef Heap PQueue;
typedef HData PQData;
void PQueueInit(PQueue *q, Prioritycomp pc);
int PQIsEmpty(PQueue *q);
void Enqueue(PQueue *q, PQData data);
int Dequeue(PQueue *q);
#endif아마 PriorityQueue는 위의 설명들을 쭉 읽어봤다면, 바로 머릿숙에서 구현이 될거다.
여기까지.
