[ch 09-2] 힙의 구현과 우선순위 큐의 완성_3(일부 코드 변경)

[주제]

- 앞서 구현한 힙 구조에서 일부분 업그레이드하기

[변경되는 부분]

- 프로그래머가 우선순위 판단 기준을 설정해놓기

- 우선순위 비교 함수를 만들어서 우선순위 비교하기

[중요]

- 우선순위 비교 함수의 기능

1. 첫 번째 인자의 우선순위가 높으면: '0'보다 큰 값을 반환

2. 두 번째 인자의 우선순위가 높으면: '0'보다 작은 값을 반환

3. 각 인자의 우선순위가 동일하면: '0'을 반환

[소스]

■ UsefulHeap.h

#ifndef SIMPLEHEAP_H_
#define SIMPLEHEAP_H_
 
#define TRUE        1
#define FALSE        0
 
#define HEAP_LEN    100
 
/*
 * 'Heap' 구조체에 통합
 */
/*
typedef struct _heapElem
{
    int pr;
    char data;
} HeapElem;
*/
 
typedef int PriorityComp(char d1, char d2);        // 인자값 1과 2의 우선순위를 비교할 포인터 함수
 
typedef struct _heap
{
    PriorityComp * comp;    // 우선순위 비교 함수를 가리키는 'comp' 선언
    int numOfData;
 
    // HeapElem heapArr[HEAP_LEN];            // (구)데이터를 저장했던 구조체 삭제
    char heapArr[HEAP_LEN];                   // (신)'char' 자료형 구조체로만 선언
} Heap;
 
// void HeapInit(Heap * ph);                  // (구)힙 초기화
void HeapInit(Heap * ph, PriorityComp pc);    // (신)인자값으로 우선순위 비교 함수 추가
int HIsEmpty(Heap * ph);    // 힙에 데이터가 비워져 있는지 확인
 
// void HInsert(Heap * ph, char data, int pr);        // (구)새로운 노드 삽입
void HInsert(Heap * ph, char data);                   // (신)데이터 자체로 우선순위가 설정되어 있기 때문에 인자값 'pr' 사용 안 함
char HDelete(Heap * ph);    // 루트노드 삭제
 
#endif

■ UsefulHeap.c

#include "UsefulHeap.h"
 
/*
// (구)힙 초기화
void HeapInit(Heap * ph) {
    ph->numOfData = 0;
}
*/
 
/*
 * 우선순위 비교에 사용할 'comp' 초기화
 */
// (신)힙 초기화
void HeapInit(Heap * ph, PriorityComp pc) {
    ph->numOfData = 0;
    ph->comp = pc;
}
 
// 힙에 데이터가 비워져 있는지 확인
int HIsEmpty(Heap * ph) {
    if (ph->numOfData == 0) {
        return TRUE;
    } else {
        return FALSE;
    }
}
 
// 현재 노드의 부모노드 인덱스 찾기
int GetParentIDX(int idx) {
    return idx / 2;
}
 
// 현재 노드의 왼쪽 자식노드 인덱스 찾기
int GetLChildIDX(int idx) {
    return idx * 2;
}
 
// 현재 노드의 오른쪽 자식노드 인덱스 찾기
int GetRChildIDX(int idx) {
    return GetLChildIDX(idx) + 1;
}
 
/*
 * [두 개의 자식노드 중 높은 우선순위의 노드 인덱스 찾기]
 * - 왼쪽 자식노드 번호가 전체 노드개수 보다 높을 경우: 자식노드가 없는 경우를 의미
 * - 왼쪽 자식노드 번호가 전체 노드개수와 동일한 경우: 왼쪽 자식노드가 존재하며, 마지막 노드를 의미
 * - 자식노드가 양쪽에 존재하고, 왼쪽 자식노드의 우선순위 숫자가
 *   오른쪽 자식노드의 우선순위 숫자보다 높을 경우: 오른쪽 자식노드의 우선순위가 높다는 것을 의미
 * - 자식노드가 양쪽에 존재하고, 우선순위 숫자가 서로 같거나 왼쪽 자식노드가 낮을 경우:
 *   왼쪽 자식노드의 우선순위가 높다는 것을 의미
 *
 * [변경된 부분]
 * - 자식노드가 양쪽에 존재하고, 왼쪽 자식노드와 오른쪽 자식노드를 비교했을 때
 *   '0 미만'이면 오른쪽 자식노드가 우선순위가 높은 것으로 판단
 *   '0 또는 이상'이면 왼쪽 자식노드가 우선순위가 높은 것으로 판단
 */
int GetHiPriChildIDX(Heap * ph, int idx) {
    if (GetLChildIDX(idx) > ph->numOfData){
        return 0;
    } else if (GetLChildIDX(idx) == ph->numOfData) {
        return GetLChildIDX(idx);
    }
    else {
    //  if (ph->heapArr[GetLChildIDX(idx)].pr
    //          > ph->heapArr[GetRChildIDX(idx)].pr) {
        if(ph->comp(ph->heapArr[GetLChildIDX(idx)],
                ph->heapArr[GetRChildIDX(idx)]) < 0) {
            return GetRChildIDX(idx);
        } else {
            return GetLChildIDX(idx);
        }
    }
}
 
/*
 * [새로운 노드 생성 및 우선순위에 맞는 자리 찾아가기]
 * - 'idx'에 마지막 노드의 위치를 저장
 * - 생성된 노드에 우선순위 숫자와 데이터 저장
 * - 생성된 노드가 루트 노드가 아닐 경우 다음을 반복
 * - 생성된 노드의 우선순위 숫자가 부모노드의 우선순위 숫자보다 낮을 경우:
 *   생성된 노드가 우선순위가 높다는 것을 의미 -> 부모노드와 위치를 교체
 * - 우선순위 숫자가 같거나 높을 경우 반복 종료
 * - 데이터 개수 1개 추가
 *
 * [변경된 부분]
 * - 'HeapElem'은 사용 안 함
 * - 현재 노드와 부모노드의 우선순위를 비교 했을 때
 *   '0 초과'이면 부모노드를 배치
 */
// void HInsert(Heap * ph, char data, int pr) {
void HInsert(Heap * ph, char data) {
    int idx = ph->numOfData + 1;
//  HeapElem nelem = {pr, data};
 
    while (idx != 1) {
    //  if (pr < (ph->heapArr[GetParentIDX(idx)].pr)) {
        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;
}
 
/*
 * [루트노드 삭제 및 우선순위에 맞는 자리 찾아가기]
 * - 루트노드의 데이터는 반환될 'retData'에 저장
 * - 마지막 노드는 루트노드 자리에 옮기지 않고 'lastElem'을 마지막 노드로 임시 설정하여 우선순위 비교
 * - 우선순위가 높은 자식노드와 비교하여 우선순위가 낮으면 위치를 교체해가며 아래로 내려감
 * - 우선순위가 더 높거나 더 이상 아래로 내려갈 수 없으면 최종적으로 위치가 고정됨
 * - 노드 전체개수를 '1' 감소하고 루트노드의 데이터는 반환
 *
 * [변경된 부분]
 * - 마지막 노드와 자식노드의 우선순위를 비교 했을 때
 *   '0 이상'이면 비교 정지
 */
char HDelete(Heap * ph) {
//  char retData = (ph->heapArr[1]).data;
    char retData = (ph->heapArr[1]);
//  HeapElem lastElem = ph->heapArr[ph->numOfData];
    char lastElem = ph->heapArr[ph->numOfData];
 
    int parentIdx = 1;
    int childIdx;
 
    while(childIdx = GetHiPriChildIDX(ph, parentIdx)) {
    //  if(lastElem.pr <= ph->heapArr[childIdx].pr)
        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 retData;
}

■ UsefulHeapMain.c

#include <stdio.h>
#include "UsefulHeap.h"
 
// 우선순위 비교 함수
int DataPriorityComp(char ch1, char ch2) {
    return ch2 - ch1;
}
 
int main(void) {
    Heap heap;
//  HeapInit(&heap);
    HeapInit(&heap, DataPriorityComp);
 
    HInsert(&heap, 'A');
    HInsert(&heap, 'B');
    HInsert(&heap, 'C');
 
    HInsert(&heap, 'D');
    HInsert(&heap, 'C');
    HInsert(&heap, 'B');
 
    while(!HIsEmpty(&heap))
        printf("%c \n", HDelete(&heap));
 
    return 0;
}

■ 실행결과

■ 첨부파일

UsefulHeap.c

UsefulHeap.h

UsefulHeapMain.c