힙

#include<iostream>
#include<conio.h>

#define HEAP_LEN 100

using namespace std;

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

typedef struct _help{
	int numofData;
	HData heapArr[HEAP_LEN];
	PriorityComp *comp;
}Heap;

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

int HIsEmpty(Heap *ph){
	if(ph->numofData==0)
		return 1;
	else
		return 0;
}

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

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

int GetRChildIDX(int idx){
	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->comp(ph->heapArr[GetLChildIDX(idx)],ph->heapArr[GetRChildIDX(idx)])<0){
			return GetRChildIDX(idx);
		}
		else
			return GetLChildIDX(idx);
}

//힙에서 데이터 삭제
HData HDelete(Heap *ph){
	HData retData=ph->heapArr[1];
	HData lastElem=ph->heapArr[ph->numofData];

	int paranetIdx=1;
	int childIdx;

	while(childIdx=GetHiPriChildIDX(ph,paranetIdx)){
		if(ph->comp(lastElem, ph->heapArr[childIdx])>=0){
			break;
		}
		ph->heapArr[paranetIdx]=ph->heapArr[childIdx];
		paranetIdx=childIdx;
	}

	ph->heapArr[paranetIdx]=lastElem;
	ph->numofData-=1;
	return retData;
}

//힙에서 데이터 삽입
void HInsert(Heap *ph, HData data){
	int idx=ph->numofData+1;

	while(idx!=1){
		if(ph->comp(data,ph->heapArr[GetParentIDX(idx)])>0){
			idx=GetParentIDX(idx);
		}
		else
			break;
	}
	ph->heapArr[idx]=data;
	ph->numofData+=1;
}

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

int main()
{
	Heap heap;
	HeapInit(&heap, DataPriorityComp);

	HInsert(&heap, 'A');
	HInsert(&heap, 'B');
	HInsert(&heap, 'C');
	cout << HDelete(&heap) << endl;

	HInsert(&heap, 'A');
	HInsert(&heap, 'B');
	HInsert(&heap, 'C');
	cout << HDelete(&heap) << endl;

	while(!HIsEmpty(&heap)){
		cout << HDelete(&heap) << endl;
	}
	getch();
	return 0;
}