힙(Heap)

#include <iostream>

typedef int Priority;

template<typename T>

class HeapElem{

public:

Priority pr;

T data;

};

template<typename T>

class Heap{

private:

HeapElem *HeapArr

int NumOfData;

public:

Heap(int NumOfHeap)

{

HeapArr = new HeapElem[NumOfHeap];

NumOfData = 0;

}

~Heap()

{

delete []HeapArr;

}

void Insert(Heap &ph, T data, Priority pr);

T Delete(Heap &ph, T data);

int GetParentIDX(int idx);

int GetLChildIDX(int idx);

int GetRChildIDX(int idx);

int GetHiChildIDX(Heap *ph, int idx)

bool is_Empty(Heap *ph);

};

template<typename T>

void Heap<T>::Insert(Heap &ph, T data, Priority pr)

{

int idx = Heap->NumOfData + 1; // Arr[0]은 버림.

HeapElem<T> Temp;

Temp.pr = pr;

Temp.data = data;

while(idx != 1)

{

// 부모가 우선순위가 낮다면(pr 값이 크다면)

if(pr < ph->HeapArr[GetParentIDX(idx)].pr)

{

ph->HeapArr[idx] = ph->HeapArr[GetParentIDX(idx)];

idx = GetParentIDX(idx);

}

else

break;

}

ph->HeapArr[idx] = Temp;

ph->NumOfData += 1;

}

template<typename T>

T Heap<T>::Delete(Heap &ph)

{

T ret_data = (ph->HeapArr[1]).data;

Heap_Elem Last_Elem = ph->HeapArr[ph->NumOfData];

int Parent = 1;

int Child;

while(Child = GetHiChildIDX(&ph, Parent))

{

if(ph->HeapArr[Child].pr >= Last_Elem.pr)

break;

ph->HeapArr[Parent] = ph->HeapArr[Child];

Parent = Child;

}

ph->HeapArr[Parent] = Last_Elem;

ph->NumOfData -= 1;

return ~;

}

template<typename T>

int GetParentIDX(int idx)

{

return idx/2;

}

template<typename T>

int GetLChildIDX(int idx)

{

return idx*2;

}

template<typename T>

int GetRChildIDX(int idx)

{

return idx*2+1;

}

template<typename T>

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->HeapArr[GetLChildIDX(idx)].pr < ph->HeapArr[GetRChildIDX(idx)].pr)

return GetLChildIDX(idx);

else

return GetRChildIDX(idx);

}

}

template<typename T>

bool Heap<T>::is_Empty(Heap *ph)

{

if(ph->NumOfData == 0)

return TRUE;

else

return FALSE;

}

int main(int argc, char *argv[])

{

Heap<int> Pri_Heap(100);

return 0;

}