Heap.h

#ifndef __HEAP_H__
#define __HEAP_H__

#define TRUE    1
#define FLASE   0

#define HEAP_LEN    100

typedef char HData;
typedef int PriorityComp(HData d1, HData d2);  // 우선순위 결정 함수 포인터
// typedef int priority;

// typedef struct _heapElem
// {
//     priority pr;
//     HData data;
// } HeapElem;

typedef struct _heap
{
    PriorityComp *comp;
    int numOfData;
    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

Heap.c

#include <stdio.h>
#include "Heap.h"

void HeapInit(Heap *ph, PriorityComp pc)
{
    ph->numOfData = 0;
    ph->comp = pc;
}

int HIsEmpty(Heap *ph)
{
    if (ph->numOfData == 0)
        return TRUE;
    return FLASE;
}

int GetParentIdx(int idx) // 부모노드의 index는 자식노드의 / 2이다.
{
    return idx / 2;
} 

int GetLChildIdx(int idx) // 자식노드의 index는 부모노드의 * 2이다.
{
    return idx * 2;
}

int GetRChildIdx(int idx) // 오른쪽 자식노드의 index는 부모노드의 * 2 + 1이다.
{
    return GetLChildIdx(idx) + 1;
}

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)
        // {
        //     return GetRChildIdx(idx);
        // }
        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 (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;
}

HData HDelete(Heap *ph)
{
    HData reData = ph->heapArr[1];
    HData 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 reData;
}

int DataPriorityComp(char ch1, char ch2)
{
    return ch2 - ch1;
}

우선순의 결정 함수

Heap.h

#ifndef __PRIORITY_QUEUE_H__
#define __PRIORITY_QUEUE_H__

#define HEAP_LEN    100

typedef char HData;
typedef int PriorityComp(HData d1, HData d2);

class Heap
{
private:
    PriorityComp *comp;
    int numOfData;
    HData heapArr[HEAP_LEN];
public:
    void HeapInit(PriorityComp pc);
    int HIsEmpty();
    int GetHiPriChildIDX(int idx);
    void HInsert(HData data);
    HData HDelete();
};
#endif

Heap.cpp

#include <iostream>
#include "Heap.h"

void Heap::HeapInit(PriorityComp pc)
{
    comp = pc;
    numOfData = 0;
}
int Heap::HIsEmpty()
{
    if (numOfData == 0)
        return true;
    return false;
}

int GetParentIdx(int idx)
{
    return idx / 2;
}

int GetLChildIdx(int idx)
{
    return idx * 2;
}

int GetRChildIdx(int idx)
{
    return GetLChildIdx(idx) + 1;
}

int Heap::GetHiPriChildIDX(int idx)
{
    if (GetLChildIdx(idx) > numOfData)
        return 0;
    else if (GetLChildIdx(idx) == numOfData)
        return GetLChildIdx(idx);
    else
    {
        if (comp(heapArr[GetLChildIdx(idx)] , heapArr[GetRChildIdx(idx)]) < 0)
            return GetRChildIdx(idx);
        else
            return GetLChildIdx(idx);
    }
}

void Heap::HInsert(HData data)
{
    int idx = numOfData + 1;

    while (idx != 1)
    {
        if (comp(data, GetParentIdx(idx)) > 0)
        {
            heapArr[idx] = heapArr[GetParentIdx(idx)];
            idx = GetParentIdx(idx);
        }
        else
            break;
    }
    heapArr[idx] = data;
    numOfData += 1;
}

HData Heap::HDelete()
{
    if (HIsEmpty())
    {
        std::cout << "no data";
        exit(0) ;
    }
    int retData = heapArr[1]; // 처음은 비워 놓기 때문에
    int lastData = heapArr[numOfData];

    int parentIdx = 1;
    int childIdx;;
    while (childIdx != 0)
    {
        childIdx = GetHiPriChildIDX(parentIdx);
        if (comp(lastData, heapArr[childIdx]) >= 0)
            break;
        
        heapArr[parentIdx] = heapArr[childIdx];
        parentIdx = childIdx;
    }
    heapArr[parentIdx] = lastData;
    numOfData--;
    return retData;
}