C로 만드는 자료구조- 배열로 구현하는 힙(Heap)

이글은 이전글과 이어집니다.

dsbook.tistory.com/255

C로 만드는 자료구조- 힙(Heap)이란?

위 글에서는 힙이란 무엇인지, 힙의 추상 자료형과 그 중 핵심인 삽입과 삭제 연산에 대해 다루었다. 이제는 실제로 코드 구현은 해볼려고 한다. 이글에서는 배열을 이용해 구현하려고 한다.

배열을 이용한 이진 트리 

 이진 트리는 자식 노드가 최대 2개 이기 때문에 규칙을 만들어 배열의 인덱스를 이용하여 부모,자식 노드간의 관계를 나타낼 수 있다. 

규칙은 다음과 같다.( 편의상 배열 인덱스의 시작은 1로 했습니다.)
1) 노드 i의 부모 노드 인덱스 = [i/2]  (단, i>1)
2) 노드 i의 왼쪽 자식 노드 인덱스 = 2 * i
3) 노드 i의 오른쪽 자식 노드 인데스 = (2*i) + 1

그림으로 나타내면 다음과 같다.

배열을 이용한 힙 구현

소스 파일 구성은 다음과 같다.

파일 이름	내용
ArrayHeap.h	구조체 및 함수 선언
ArrayHeap.cpp	함수 구현
ArrayHeapMain.cpp	main 함수 실행

1.ArrayHeap.h

구현하기 앞서 힙의 추상자료형을 다시 한번 보자

이름		입력	출력	설명
힙 생성	createHeap()	힙의 크기 n	힙 H	최대 n개의 원소를 가질 수 있는 힙 H 생성
힙 삭제	deleteHeap()	힙 H	N/A	힙 메모리 해제
노드 추가	inseertHeap()	힙 H 원소 e	성공/실패 여부	힙에 새로운 원소 추가
노드 제거/반환	deleteHeapNode()	힙 H	원소 e	힙의 루트 노드 제거 후 반환

코드 구현은 다음과 같다.

#pragma once
#include<iostream>
#include<cstring>
using namespace std;
#define TRUE 1
#define FALSE 0

typedef struct HeapNode {
	int key;
};

typedef struct ArrayMaxHeap {
	int maxNodeCount;		//최대 노드 개수
	int currentNodeCount;	//현재 노드 개수
	HeapNode *pElement;		//노드들을 저장하고 있는 1차원 배열
};

ArrayMaxHeap* createMaxHeap(int _maxNodeCount);					//힙 생성 함수
void deleteMaxHeap(ArrayMaxHeap *pMaxHeap);						//힘 삭제 함수
void insertMaxHeap(ArrayMaxHeap* pMaxHeap, HeapNode element);	//노드 추가 함수 
HeapNode* deleteMaxHeapAH(ArrayMaxHeap* pMaxHeap);				//노드 제거 및 반환 함수

2.ArrayHeap.cpp

 - createMaxheap()

ArrayMaxHeap* createMaxHeap(int _maxNodeCount) {					//힙 생성 함수
	ArrayMaxHeap *pReturn = NULL;
	
	if (_maxNodeCount > 0) {
		pReturn = (ArrayMaxHeap *)malloc(sizeof(ArrayMaxHeap));
		if (pReturn != NULL) {
			pReturn->maxNodeCount = _maxNodeCount;
			pReturn->currentNodeCount = 0;

			pReturn->pElement = (HeapNode *)malloc(sizeof(HeapNode)*(_maxNodeCount + 1));
			memset(pReturn->pElement, 0, sizeof(HeapNode)*(_maxNodeCount + 1));
		}
	}
	else {
		printf("최대 원소 개수는 0보다 커야 합니다.\n");
	}
	return pReturn;
}

 힙을 생성하는 함수이다. 여기서 주의해야 할점은 배열에 메모리를 할당할 때 최대 사이즈 + 1 을 해주는 것이다. 왜냐하면 앞서 인덱스 0이 시작이 아니라 1을 시작으로 했기 때문이다.

- insertMaxheap()

삽입 연산은 2단계로 이루어진다.

1단계: 트리의 마지막 자리에 임시저장
2단계: 부모 노드와 키 값 비교 및 이동

void insertMaxHeap(ArrayMaxHeap* pMaxHeap, HeapNode element) {	//노드 추가 함수 
	if (pMaxHeap != NULL) {
		if (pMaxHeap->currentNodeCount == pMaxHeap->maxNodeCount) {
			printf("힙이 가득차 있습니다\n");
			return;
		}

		pMaxHeap->currentNodeCount++;
		int i = pMaxHeap->currentNodeCount;//1단계

		while ((i != 1) && (element.key > pMaxHeap->pElement[i / 2].key)) { //2단계
			pMaxHeap->pElement[i] = pMaxHeap->pElement[i / 2];
			i /= 2;
		}
		pMaxHeap->pElement[i] = element;
	}
}

 가장 먼저 힙이 가득차 있는지 확인 후 연산을 실행 한다. 힙이 가득차 있지 않으면 currentNodeCount에 1을 더해주고 
변수 i 에 완전 이진 트리의 마지막 위치의 인덱스를 준다.(임시 저장) 임시 저장을 한 후 while 문을 이용해 최대 트리의 특성을 유지하게 해준다.

- deleteMaxheapAH()

삭제 연산은 3단계로 이루어진다.

1단계: 루트 노드의 삭제
2단계: 트리 마지막 자리 노드의 임시 이동
3단계: 자식 노드와 키 값 비교 및 이동

HeapNode* deleteMaxHeapAH(ArrayMaxHeap* pMaxHeap) {				//노드 제거 및 반환 함수
	HeapNode* pReturn = NULL;
	HeapNode* pTemp = NULL;

	int parent = 0;
	int child = 0;

	if (pMaxHeap != NULL && pMaxHeap->currentNodeCount > 0) {
		pReturn = (HeapNode*)malloc(sizeof(HeapNode));
		if (pReturn != NULL) {
			*pReturn = pMaxHeap->pElement[1];

			int i = pMaxHeap->currentNodeCount;
			pTemp = &(pMaxHeap->pElement[i]);
			pMaxHeap->currentNodeCount--;

			parent = 1;
			child = 2;

			while (child <= pMaxHeap->currentNodeCount) {
				if ((child < pMaxHeap->currentNodeCount) && (pMaxHeap->pElement[child].key < pMaxHeap->pElement[child + 1].key)) {
					child++;
				}

				if (pTemp->key >= pMaxHeap->pElement[child].key) {
					break;
				}
				pMaxHeap->pElement[parent] = pMaxHeap->pElement[child];
				parent = child;
				child *= 2;
			}
			pMaxHeap->pElement[parent] = *pTemp;
		}
	}
	return pReturn;
}

 

- deleteMaxheap()

void deleteMaxHeap(ArrayMaxHeap *pMaxHeap) {						//힘 삭제 함수
	if (pMaxHeap != NULL) {
		if (pMaxHeap->pElement != NULL) {
			free(pMaxHeap->pElement);
		}
		free(pMaxHeap);
	}
}

 힙의 메모리를 해제 해주는 함수이다. 힙의 메모리를 없애기 전에 먼저 배열을 해제 시켜줘야 하는 것을 생각해야한다.

3.ArrayHeapMain.cpp

실제로 최대 힙을 만들고 힙 연산 함수들을 사용해 보았다. 

#include"arrayheap.h"

void display(ArrayMaxHeap* pMaxHeap) {
	if (pMaxHeap != NULL) {
		for (int i = 1; i <= pMaxHeap->currentNodeCount; i++) {
			printf("[%d],%d\n", i, pMaxHeap->pElement[i].key);
		}
	}
}

int main()
{
	int maxHeapSize = 20;

	ArrayMaxHeap* pMaxHeap = NULL;

	HeapNode *pNode = NULL;
	HeapNode n1 = { 15 };
	HeapNode n2 = { 5 };
	HeapNode n3 = { 11 };
	HeapNode n4 = { 1};
	HeapNode n5 = { 3 };
	HeapNode n6 = { 9 };
	HeapNode n7 = { 7 };


	pMaxHeap = createMaxHeap(maxHeapSize);
	insertMaxHeap(pMaxHeap, n1);
	insertMaxHeap(pMaxHeap, n2);
	insertMaxHeap(pMaxHeap, n3);
	insertMaxHeap(pMaxHeap, n4);
	insertMaxHeap(pMaxHeap, n5);
	insertMaxHeap(pMaxHeap, n6);
	insertMaxHeap(pMaxHeap, n7);

	printf("MAX HEAP:\n");
	display(pMaxHeap);

	pNode = deleteMaxHeapAH(pMaxHeap);
	printf("deleteMaxHeapAH()-[%d]\n", pNode->key);
	printf("MAX HEAP:\n");
	display(pMaxHeap);

	deleteMaxHeap(pMaxHeap);

    return 0;
}

결과는 다음과 같다.