힙(Heap)정의, 힙 추가 연산

힙이란?

-바이너리 트리의 한 종류

-루트 노드가 언제나 트리의 최대값(각 노드의 값이 자식 노드의 값보다 크거나 같음) 또는 최소값

-힙은 완전 바이너리 트리다. 중간에 빈 노드가 없다.

 

구분	조건	루트 노드의 키 값
최대 힙(Max Heap)	부모 노드의 키 값>=자식 노드의 키 값	트리 중에서도 최댓값
최소 힙(Min Heap)	부모 노드의 키 값<=자식 노드의 키 값	트리 중에서도 최솟값

 

힙은 느슨한 정렬 상태를 의미한다. -> 각 노드가 모든 하위 레벨의 노드보다 크거나 같지 않음.

 

typedef struct ArrayHeapType
{
	int maxCount;
    int currentCount;
    HeapNode *pData;
    }ArrayMaxHeap, ArrayMinHeap;
    
 ArrayMaxHeap* createArrayMaxHeap(int maxCount)
 {
 	ArrayMaxHeap *pReturn = NULL;
    if(maxCount>0){
    	pReturn = (ArrayMaxHeap*)malloc(sizeof(ArrayMaxHeap));
        pReturn->maxCount=maxCount;
        pReturn->currentCount=0;
        pReturn->pData = (HeapNode*)malloc(sizeof(HeapNode)*(maxCount+1)); //여기서 설명 있음
        memset(pReturn->pData,0,sizeof(HeapNode)*(maxCount+1));
        }
        else{
        printf("최대 원소 개수는 0보다 커야 합니다.\n");
        }
        return pReturn;
}

전에 포스팅 해왔던 이진트리와 달리, 힙은 배열을 사용한다.

하지만 원래 배열의 첫번째 인덱스는 0이지 않나..! 이대로 사용할 수 없고 1을 더해줘야 한다.

그 이유는, 힙의 각각의 노드는 데이터+배열 인덱스가 지정되어 있는데 인덱스가 0인 노드는 존재하지 않기 때문이다.

인덱스는 1부터 시작하기 때문에 maxCount+1로 작성해주는 것이다.

 

 

 

 

힙 추가 연산

1. 트리의 마지막 자리에 임시 저장 (가장 큰 레벨의 가장 오른쪽 위치)

2. 부모 노드의 키 값과 비교하여 이동시킴

 

int insertMaxHeapAH(ArrayMaxHeap* pHeap, int value)
{
	int i=0;
    
    if(pHeap!=NULL){
    	if(pHeap->currentCount == pHeap->maxCount){
        	printf("오류, 히프가 가득 찼습니다.[%d]",pHeap->maxCount);
            return 0;
            }
            
        pHeap->currentCount++;
        i = pHeap->currentCount; //i는 힙의 마지막 노드를 가리키는 위치 인덱스 
        while((i!=1) && (value > pHeap->pData[i/2].data)){ //새로 추가된 값이 부모 노드보다 크다.
        	pHeap->pData[i]=pHeap->pData[i/2]; //부모 노드의 값을 현재 위치로 이동
            i/=2; //부모 노드 위치로 이동
        }
        pHeap->pData[i].data=value;
}

	return i;
 }