Heap 구현-C

1. Heap.h

#ifndef  HEAP_H
#define HEAP_H
 
#include <stdio.h>
 
#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 int PriorityComp(HData d1, HData d2);
 
typedef struct _heap {
 
    PriorityComp* comp;
    int numOfData;
    HData heapArr[HEAP_LEN];
}Heap;
 
void HeapInit(Heap* heap,PriorityComp pc);
int IsH_Empty(Heap* heap);
 
int DataPriorityComp(HData c1, HData c2);
 
void HInsert(Heap* heap, HData data);
HData HDelete(Heap* heap);
 
int GetParentIDX(int idx);
int GetLChildIDX(int idx);
int GetRChildIDX(int idx);
 
 
#endif // ! HEAP_H
 

2. Heap.c

#include "Heap.h"
 
/*
HeapInit
heap의 관련 데이터를 초기화한다.
*/
void HeapInit(Heap* heap,PriorityComp pc) {
 
    heap->numOfData = 0;
    heap->comp = pc;
}
/*
IsH_Empty
heap의 데이터가 비어있는지 확인하는 함수.
*/
int IsH_Empty(Heap* heap) {
 
    return (heap->numOfData = 0) ? TRUE : FALSE;
}
 
int GetParentIDX(int idx) {
 
    return idx / 2;
}
 
int GetLChildIDX(int idx) {
    
    return idx * 2;
}
 
int GetRChildIDX(int idx) {
 
    return idx * 2 + 1;
}
 
/*
DataPriorityComp
데이터의 우선순위를 판단하는 함수.
*/
int DataPriorityComp(HData c1, HData c2) {
 
    return c2 - c1;
}
 
/*
GetHighPriChildIDX;
해당 노드의 자식노드 중 큰 IDX를 반환하는 함수.
*/
int GetHighPriChildIDX(Heap* heap, int idx) {
 
    int LChildIDX = GetLChildIDX(idx);
    int RChildIDX = GetRChildIDX(idx);
 
    /*
    윈쪽 자식노드의 index값이 전체 노드의 개수(numOfData)보다
    크다면, 즉, 윈쪽 자식 노드가 없다면, 0을 반환.
    */
    if (LChildIDX > heap->numOfData)
        return 0;
 
    /*
    윈쪽 자식노드의 idx값과 전체 노드의 개수와 같다는 것은,
    LChildIDX가 가장 높은 레벨의 노드라는 것이다.
    그래서 우선순위를 비교할 또 다른 노드가 없다.
    (자식노드가 자기자신 뿐)
    자기 자신을 return.
    */
    else if (LChildIDX == heap->numOfData)
        return LChildIDX;
    /*
    비교할 두개의 노드가 있을 경우. 즉, 비교할 노드의 가장 일반적인 경우
    두개의 우선순위를 비교한다.
    */
    else {
        if (heap->comp(heap->heapArr[LChildIDX], heap->heapArr[RChildIDX]) < 0)
            return RChildIDX;
        else
            return LChildIDX;
    }
}
 
void HInsert(Heap* heap, HData data) {
 
    int newIdx = heap->numOfData + 1;
    HData newElem = data;
 
    while (newIdx != 1) {// newIdx!=0은 안된다. 왜나하면 idx=1의 paraentIdx는 없어서...
        int parentIdx = GetParentIDX(newIdx);
        /*
        두개의 우선순위를 비교하고, 만약 insert하는 data의 우선순위가 더 크다면,
        두개의 노드의 데이터를 바꾼다. 
        그리고 parentIdx의 부모노드와 비교하기 위해서,
        newIdx=parentIdx를 넣는다.
        */
        if (heap->comp(data, heap->heapArr[parentIdx]) > 0) {
            heap->heapArr[newIdx] = heap->heapArr[parentIdx];
            newIdx = parentIdx;
        }
        else {
            heap->heapArr[newIdx] = data;
            break;
        }
    }
 
    heap->numOfData++;
}
 
HData HDelete(Heap* heap) {
    /*
    heap에서 노드의 삭제는 루트노드의 삭제이다.
    우선순위가 가장 큰 노드.
    루트노드를 삭제하고 그 자리에 마지막 idx의 노드가 있다고 가정한다.

    */
    HData retData = heap->heapArr[1];
    HData lastElem = heap->heapArr[heap->numOfData];
 
    int childIdx, parentIdx = 1;
 
    /*
    GetHighPriChildIDX에서 0을 return하면, 즉, 입력된 주소가
    가장 높은 레벨의 노드라면 while문을 종료한다. 또는, lastElem의 우선순위가
    더 낮거나 같다면 break. 그렇지 않다면,(비교할 노드가 있고, 우선순위도 lastElem이 앞선다면)
    부모노드에 자식노드의 데이터를 넣는다. 그리고 자식노드의 그 자식노드를 비교하기 위해서
    새로운 부모노드는 자식노드가 된다.
    */
    while (childIdx = GetHighPriChildIDX(heap, parentIdx)) {
        if (heap->comp(lastElem, heap->heapArr[childIdx]) >= 0)
            break;
 
        heap->heapArr[parentIdx] = heap->heapArr[childIdx];
        parentIdx = childIdx;
    
    }
 
    heap->heapArr[childIdx] = lastElem;
    heap->numOfData--;
 
    return retData;
}
 
 

(참고 : 자료구조, 윤성우)