#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;
}
'자료' 카테고리의 다른 글
[자료구조] Stack (0) | 2015.12.05 |
---|---|
Double Free Bug (1) | 2015.10.03 |
[C++] PE Viewer 미완 (0) | 2015.07.05 |
MIPS Assemble (0) | 2014.11.23 |
Client Socket (0) | 2014.10.30 |