enum eMenu
{
eInsert = 1,
eDel,
ePrint,
eExit,
};
static const int ARRAY_MIN = 0;
static const int ARRAY_MAX = 10;
class CHeapManager
{
public:
CHeapManager();
~CHeapManager();
int returnParent(int nGetData);
int returnLeft(int nGetData);
int returnRight(int nGetData);
int returnPreference(int nGetIndex);
int Start();
void Insert();
void Delete();
void Print();
private:
static int Heap[ARRAY_MAX];
int m_nDataNumber; //저장된 데이터 갯수
};
int CHeapManager::Heap[ARRAY_MAX];
CHeapManager::CHeapManager()
{
cout << "생성자 " << endl;
m_nDataNumber = 0;
}
CHeapManager::~CHeapManager()
{
cout << "소멸자" << endl;
}
int CHeapManager::Start()
{
}
int CHeapManager::returnParent(int nGetData)
{
return nGetData / 2;
}
int CHeapManager::returnLeft(int nGetData)
{
return nGetData * 2;
}
int CHeapManager::returnRight(int nGetData)
{
return (nGetData * 2) + 1;
}
int CHeapManager::returnPreference(int nGetIndex)
{
//하나도 없을때
//현재 데이터의 값보다 인덱스가 큰 경우에는..특히 왼쪽부터
//채워지는 트리의 특성상 왼쪽보다 크다면 단말노드이다.
if (returnLeft(nGetIndex) > m_nDataNumber)
{
//0이 반환하게 되면 더이상 delete함수에서 while가 참이 안되
//바로 나가게 되지
return NULL;
}
//왼쪽에 하나 있을떄..
//생각해봐라 2개 넣으면 datanumber는 2기 될테고..
//왼쪽 인덱스역시 2이니까..왼쪽 하나가 있다는것임..
else if (returnLeft(nGetIndex) == m_nDataNumber)
{
return returnLeft(nGetIndex);
}
else
{
if (Heap[returnLeft(nGetIndex)] > Heap[returnRight(nGetIndex)])
return returnRight(nGetIndex);
else
return returnLeft(nGetIndex);
}
}
void CHeapManager::Insert()
{
if (ARRAY_MAX <= m_nDataNumber)
{
cout << "가득 찼다" << endl;
}
else
{
//마지막 인덱스에 값을 넣고 올라가는거다
int nIndex = m_nDataNumber + 1;
int nData;
cin >> nData;
while (nIndex != 1)
{
if (Heap[returnParent(nIndex)] > nData)
{
Heap[nIndex] = Heap[returnParent(nIndex)];
nIndex = returnParent(nIndex);
}
else
break;
}
Heap[nIndex] = nData;
++m_nDataNumber;
}
}
void CHeapManager::Delete()
{
if (0 >= m_nDataNumber)
{
cout << "비어있다" << endl;
}
else
{
//최상위 인덱스를 저장해두고.
//마지막 노드의 값을 가져온다.
//실제 노드들을 계속 바꾸는게 아니라 값을 비교하고
//마지막 노드가 들어가야할 인덱스만 바꾸는것이다.
int nBestParentIndex = ARRAY_MIN + 1;
int nLastNodeData = Heap[m_nDataNumber];
int nchildIndex = returnPreference(nBestParentIndex);
while (nchildIndex = returnPreference(nBestParentIndex))
{
//더이상 내려갈 경우 자식이 마지막 노드보다 커지게 된다.
if (Heap[nchildIndex] >= nLastNodeData)
{
//탈출
break;
}
else
{
Heap[nBestParentIndex] = Heap[nchildIndex];
nBestParentIndex = nchildIndex;
}
}
}
}