열혈 자료구조 - 9.2 힙의 구현과 우선순위 큐의 완성(2)

배열 기반의 힙

- 루트노드부터 1번으로 위쪽에서 아래쪽으로 왼쪽에서 오른쪽으로 인덱스를 매겨서 배열에 저장

- 데이터 삽입, 삭제를 위해서 마지막 인덱스 값을 저장하고 있어야 함

- 0번째 인덱스는 구현의 편의를 위해 비워둠 (구현자 마음)

- 왼쪽 자식 노드의 인덱스 값 = 부모 노드의 인덱스 값 x 2

- 오른쪽 자식 노드의 인덱스 값 = 부모 노드의 인덱스 값 x 2 + 1

- 부모 노드의 인덱스 값 = 자식 노드의 인덱스 값 / 2

 

힙의 구현

- 구조체

    -> Heap 구조체는 힙과 관련이 있는 구조체

    -> heapElem 구조체는 우선순위 큐와 관련이 있는 구조체

typdef char HData;
typdef int Priority;	// 우선 순위

typedef struct _heapElem {
    Priority pr;	// 값이 작을수록 높은 우선순위라고 구현
    HData data;
} HeapElem;		 // 힙에 저장되는 데이터의 기본 단위

typedef struct _heap {
    int numOfData;			// 힙의 개수는 마지막 노드의 번호와 같음
    HeapElem heapArr[HEAP_LEN];
} Heap;			// 힙을 나타내는 구조체

- 초기화 및 기본 함수

void HeapInit(Heap * ph)
{
	ph->numOfData = 0;
} // 초기화

int HIsEmpty(Heap * ph)
{
	if(ph->numOfData == 0) { return TRUE; }
	else		       { return FALSE; }
} // 비어있는지 확인

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; }
        // 1단계 : 자식 노드가 없다는 의미
        
	else if(GetLChildIDX(idx) == ph->numOfData)
		return GetLChildIDX(idx);
        // 2단계 : 좌측 자식 노드만 있다는 의미

	else
	{
		if(ph->heapArr[GetLChildIDX(idx)].pr > ph->heapArr[GetRChildIDX(idx)].pr) {
			return GetRChildIDX(idx);
                } // 우측 자식 노드의 우선 순위가 높은 경우(pr의 값이 작은 경우)
                else {
                    return GetLChildIDX(idx);
                } // 좌측 자식 노드의 우선 순위가 높은 경우
	}
}

    -> 1단계 설명

        * 만약 2번 인덱스의 노드가 두 자식 노드를 비교하면 2번 노드의 GetLChildIDX의 값은 4가 되고 현재 힙의

numOfData는 4이므로 자식노드가 있다고 판단

        * 만약 4번 인덱스의 노드가 두 자식 노드를 비교하면 2번 노드의 GetLChildIDX의 값은 8이 되고 현재 힙의 numOfData는 4이므로 자식노드가 없다고 판단

    -> 2단계 설명 : 2번 노드에서 GetLeftIDX의 값 4와 numOfData 4가 같으므로 좌측 자식 노드만 있다고 판단

- 삽입

    -> 이전 설명과는 달리 마지막에 먼저 노드를 박아놓지 않음

    -> 인덱스 값만 가지고 부모노드와 비교하면서 값을 복사하면 됨

void HInsert(Heap * ph, HData data, Priority pr)
{
	int idx = ph->numOfData+1;      // 현재 마지막 노드의 다음 위치
        HeapElem nelem = {pr, data};

	while(idx != 1)
	{
		if(pr < (ph->heapArr[GetParentIDX(idx)].pr))        // 새 노드의 우선순위가 높은 경우
		{
			ph->heapArr[idx] = ph->heapArr[GetParentIDX(idx)];      
            // 마지막 노드가 될 위치에 부모의 데이터를 복사
			idx = GetParentIDX(idx);        // 부모노드 인덱스를 받음
		}
		else        // 부모 노드가 우선 순위가 높은 경우
		{
			break;      // 반복문을 빠져나옴
		}
	}
	
	ph->heapArr[idx] = nelem;       // 마지막 위치에 새 데이터를 넣음
	ph->numOfData += 1;
}

- 삭제

    -> 삽입처럼 이전 설명과는 달리 마지막 노드를 루트 노드 위치로 이동시키지 않음

    -> 삭제의 과정에서는 따로 노드끼리 스왑을 실제로 하지는 않음

    -> 데이터만 복사해서 이동

HData HDelete(Heap * ph)
{
	HData retData = ph->heapArr[1].data;     // 루트노드의 데이터
	HeapElem lastElem = ph->heapArr[ph->numOfData];        // 마지막 노드

	int parentIdx = 1;      // 마지막 노드가 위치해야 하는 인덱스 (처음에는 루트로 가야하니 1)
	int childIdx;

        // 마지막 노드를 루트 노드로 옮기는 작업을 굳이 해주지 않음        
        
	while(childIdx = GetHiPriChildIDX(ph, parentIdx)) // 자식노드의 우선순위 비교
	{
		if(lastElem.pr <= ph->heapArr[childIdx].pr)     // 마지막 노드와 자식 노드를 비교
			break;      // 마지막 노드가 우선순위가 높으면 반복문을 빠져나옴

		ph->heapArr[parentIdx] = ph->heapArr[childIdx];     
                // 자식 노드가 우선 순위가 더 높다면 자식 노드가 부모 노드위치로 이동
		parentIdx = childIdx;       
                // 자식 노드의 인덱스 값을 부모 인덱스 값으로 저장 
                // 자식이었던 것이 다시 부모가 되기 위해서
	}

	ph->heapArr[parentIdx] = lastElem;  // 마지막으로 저장된 부모노드의 위치에 마지막 노드를 저장
	ph->numOfData -= 1;
	return retData;     // 원래 루트 노드였던 노드의 값
}

- main

    -> 이 코드에 단점은 구현하는 사람이 직접 우선순위를 부여하고 있음

int main(void)
{
	Heap heap;
	HeapInit(&heap);

	HInsert(&heap, 'A', 1);
	HInsert(&heap, 'B', 2);
	HInsert(&heap, 'C', 3);
	printf("%c \n", HDelete(&heap));

	HInsert(&heap, 'A', 1);
	HInsert(&heap, 'B', 2);
	HInsert(&heap, 'C', 3);
	printf("%c \n", HDelete(&heap));

	while(!HIsEmpty(&heap))
		printf("%c \n", HDelete(&heap));

	return 0;
}