[자료구조, C] 배열 기반의 힙(Heap) 구현

<힙(Heap) 구현>

[Heap.h]

/*
* 비선형 자료구조 - 배열 기반의 힙(Heap)
* 파일명: Heap.h
* 파일 버전: 0.2
* 작성자: Sevenshards
* 작성 일자: 2023-11-24
* 이전 버전 작성 일자: 2023-11-24
* 버전 내용: 우선 순위 판단 기준을 힙에 설정할 수 있도록 함수 포인터로 변경
* 이전 버전 내용: 간단한 힙의 구현
*/

#ifndef __HEAP_H__
#define __HEAP_H__

#define TRUE 1
#define FALSE 0

#define HEAP_LEN 100

typedef char HData; // 힙에 저장될 데이터를 HData라고 별칭
typedef int PriorityComp(HData d1, HData d2); // 힙에서 사용될 우선 순위

// 힙 구조체 정의
typedef struct _heap
{
	PriorityComp* comp; // 우선 순위 기준을 판단할 함수 포인터 변수 선언
	int numOfData; // 힙의 데이터 갯수
	HData heapArr[HEAP_LEN]; // 배열 기반의 힙
} Heap;

void HeapInit(Heap* ph, PriorityComp pc); // 힙의 초기화
int HisEmpty(Heap* ph); // 힙이 비었는지 확인

void HInsert(Heap* ph, HData data); // 힙에 데이터 삽입
HData HDelete(Heap* ph); // 힙에 데이터 삭제

#endif

 

[Heap.c]

/*
* 비선형 자료구조 - 배열 기반의 힙(Heap)
* 파일명: Heap.c
* 파일 버전: 0.2
* 작성자: Sevenshards
* 작성 일자: 2023-11-24
* 이전 버전 작성 일자: 2023-11-24
* 버전 내용: 우선 순위 판단 기준을 힙에 설정할 수 있도록 함수 포인터로 변경
* 이전 버전 내용: 간단한 힙의 구현
*/
#include "Heap.h"

// 힙의 초기화
// 우선 순위 기준을 판별할 함수까지 받아서 초기화
void HeapInit(Heap* ph, PriorityComp pc)
{
	ph->numOfData = 0;
	ph->comp = pc; // 우선 순위 비교에 사용될 함수 등록
}

// 힙이 비었는지 확인
int HisEmpty(Heap* ph)
{
	if (ph->numOfData == 0)
		return TRUE;
	else
		return FALSE;
}

// 부모 노드의 인덱스 값 반환
// 부모 노드의 인덱스 값 = 자식 노드의 인덱스 값 / 2 (정수형 나눗셈)
int GetParentIDX(int idx)
{
	return idx / 2;
}

// 왼쪽 자식 노드의 인덱스 값 반환
// 왼쪽 자식 노드의 인덱스 값 = 부모 노드의 인덱스 값 * 2
int GetLChildIDX(int idx)
{
	return idx * 2;
}

// 오른쪽 자식 노드의 인덱스 값 반환
// 오른쪽 자식 노드의 인덱스 값 = (부모 노드의 인덱스 값 * 2) + 1
int GetRChildIDX(int idx)
{
	return GetLChildIDX(idx) + 1;
}

// 두 개의 자식 노드 중 높은 우선순위의 자식 노드 인덱스 값 반환
// 우선 순위의 경우 정수 값이 작을수록 높은 우선순위를 나타낸다고 가정
int GetHiPriChildIDX(Heap* ph, int idx)
{
	// 힙은 "완전 이진트리" 이므로 오른쪽 자식노드만 있는 경우는 절대 없음.
	// 자식 노드가 하나도 없다면, 단말 노드가 됨.
	// 만약 왼쪽 자식 노드의 인덱스가 힙에 저장된 노드의 수를 넘어섰다면?
	// 해당 노드는 단말 노드가 되므로 0을 반환
	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); // 왼쪽 자식 노드의 우선 순위가 높다면
	}
}

// 힙에 데이터 삽입
void HInsert(Heap* ph, HData data)
{
	int idx = ph->numOfData + 1; // 가장 마지막 노드로 생성되므로 현재 데이터 갯수보다 하나 큰 인덱스로 초기화
	
	// 새로운 노드가 저장될 위치가 루트 노드의 위치가 아닐때까지 반복문을 수행
	while (idx != 1)
	{
		// 새로 생성된 노드와 부모 노드의 우선순위를 비교
		if (ph->comp(data, ph->heapArr[GetParentIDX(idx)]) > 0) // 새로 생성된 노드의 우선 순위가 높다면
		{
			ph->heapArr[idx] = ph->heapArr[GetParentIDX(idx)]; // 기존의 부모 노드의 레벨을 하나 내린다 -> 실제로 레벨을 내림
			idx = GetParentIDX(idx); // 새로 생성된 노드의 레벨을 하나 올린다 -> 인덱스만 변경, 실제로 레벨이 올라간 상황은 아님
		}
		else
			break; // 우선 순위가 높지 않다면 반복문 종료
	}
	// 반복문 종료 후
	ph->heapArr[idx] = data; // 위의 반복문에 의해 갱신된 idx 위치에 새로 생성된 노드를 저장
	ph->numOfData += 1; // 데이터 갯수 증가
}

// 힙에 데이터 삭제
HData HDelete(Heap* ph) 
{
	HData rData = ph->heapArr[1]; // 루트 노드를 삭제하므로 힙에서 인덱스가 1인 데이터를 가져온다.
	HData lastElem = ph->heapArr[ph->numOfData]; // 그리고 힙에서 마지막 노드를 가리키기 위해 인덱스는 numOfData로 한다.

	int parentIdx = 1; // 마지막 노드를 루트 노드로 올려보내게 되므로 인덱스를 1로 초기화, 마지막 노드가 저장될 위치 정보가 담기는 변수
	int childIdx; // 비교를 위해 사용할 자식 노드 인덱스 변수


	// 루트 노드부터 시작해서 자식 노드와 우선 순위를 비교
	while (childIdx = GetHiPriChildIDX(ph, parentIdx))
	{
		if (ph->comp(lastElem, ph->heapArr[childIdx]) >= 0) // 마지막 노드와 우선 순위를 비교
			break; // 마지막 노드의 우선순위가 높거나 같다면 반복문 종료
		ph->heapArr[parentIdx] = ph->heapArr[childIdx]; // 그렇지 않다면 현재 자식 노드의 레벨을 하나 올린다. -> 실제로 레벨을 올림
		parentIdx = childIdx; // 그리고 마지막 노드가 저장될 위치를 한 레벨 아래로 낮춘다. -> 인덱스만 변경, 실제로 변경은 안함
	}

	// 반복문이 끝나고 난 후
	ph->heapArr[parentIdx] = lastElem; // 위에서 갱신된 parentIdx 위치에 마지막 노드를 해당 위치에 저장 
	ph->numOfData -= 1; // 데이터 갯수 감소
	return rData; // 루트 노드의 데이터 반환
}

 

[HeapMain.c]

/*
* 비선형 자료구조 - 배열 기반의 힙(Heap)
* 파일명: HeapMain.c
* 파일 버전: 0.2
* 작성자: Sevenshards
* 작성 일자: 2023-11-24
* 이전 버전 작성 일자: 2023-11-24
* 버전 내용: 우선 순위 판단 기준을 힙에 설정할 수 있도록 함수 포인터로 변경
* 이전 버전 내용: 간단한 힙의 구현
*/
#include <stdio.h>
#include "Heap.h"

int DataPriorityComp(char ch1, char ch2)
{
	//return ch2 - ch1; // 오름차순
	return ch1 - ch2; // 내림차순
}

int main()
{
	Heap heap;
	HeapInit(&heap, DataPriorityComp); // 힙 초기화                                                                               

	HInsert(&heap, 'A'); // 문자 'A'를 저장
	HInsert(&heap, 'B'); // 문자 'B'를 저장
	HInsert(&heap, 'C'); // 문자 'C'를 저장
	printf("%c \n", HDelete(&heap)); // Heap에서 삭제되는 문자 확인

	// 2회차 저장
	HInsert(&heap, 'A'); // 문자 'A'를 저장
	HInsert(&heap, 'B'); // 문자 'B'를 저장
	HInsert(&heap, 'C'); // 문자 'C'를 저장
	printf("%c \n", HDelete(&heap)); // Heap에서 삭제되는 문자 확인

	while (!HisEmpty(&heap))
		printf("%c \n", HDelete(&heap)); // Heap에서 삭제되는 문자 확인

	return 0;
}

 

힙을 구현하기 전에 책에서 본 챕터 제목이 '우선순위 큐(Priority Queue)와 힙(Heap)' 이었다.

그래서 이건 또 새로운 종류의 큐인가 싶었다. 그런데 이게 웬걸?

큐는 큐인데 좀 희한한 큐였다.

데이터가 들어가고 나가는건 큐랑 똑같다.

다만 우선순위 큐는 들어간 순서랑 무관하게 우선순위가 높게 부여된 데이터가 먼저 나오는 것이다.

그리고 이를 구현하는 방법에는 배열, 연결 리스트, 그리고 힙(Heap)을 이용한 방법이 있다는 것이다.

배열이나 연결 리스트로도 얼마던디 우선순위 큐를 구현할 수는 있다.

하지만, 문제점이 있다.

 

1) 배열은 데이터의 삽입이나 삭제 과정에서 데이터를 한 칸씩 뒤로 밀거나 앞으로 당겨야하는 문제가 있다.

2) 삽입의 위치를 찾기 위해서 배열에 저장된 모든 데이터와의 우선순위 비교를 진행하는 경우가 있다.

 

그럼 연결 리스트로 했을 때는 1번의 문제는 해결이 되지만 마찬가지로 2번의 문제가 해결이 되질 않는다.

그렇기 때문에 데이터의 수가 많아지면 많아질수록 성능 저하의 원인이 될 수 있다.

그래서 힙(Heap)을 이용하여 구현하는 방법이 가장 일반적이라고 한다.

 

[힙(Heap)이란?]

힙이라는 자료구조는 이진 트리이면서, 완전 이진트리다.

그리고 독특한 특성을 가지고 있는데, 그 특성은 이렇다.

[모든 노드에 저장된 값은 자식 노드에 저장된 값보다 크거나 같아야 한다. 즉, 루트 노드에 있는 값은 가장 커야한다.]

여기서 값은 값 그 자체가 될 수도 있지만, 우선 순위로 볼 수도 있다.

그래서 값을 우선순위로 바꾸게 되면 우선순위 큐에 가장 적합한 형태가 된다.

추가로, 루트 노드로 올라갈수록 값이 커지는 형태의 힙을 최대 힙(max heap)이라고 한다.

반대의 경우는 최소 힙(min heap)이라고 부른다.

 

[힙에서의 데이터 저장과 삭제 과정]

우선 힙은 다음과 같은 조건을 항상 유지해야 한다.

 

1. 완전 이진 트리일 것

2. 우선순위 관계를 유지할 것

 

힙에서 들어오는 새로운 데이터(노드)는 다음의 과정을 거쳐서 추가가 된다.

1) 새로 들어온 데이터(노드)는 우선순위가 가장 낮다고 가정하여, 마지막 위치(트리의 최고 레벨의 최후단)에 저장한다.

2) 부모 노드와 우선순위를 비교하여 위치가 바뀌어야 한다면 위치를 바꾼다.

3) 바꾼 이후에도 부모 노드와 우선 순위를 비교하여 위치를 바꾼다.

4) 자신의 위치를 찾을 때까지 3)의 과정을 반복한다.

 

그리고 힙에서 데이터를 삭제하는 과정 다음과 같은 사항을 고려해야한다.

1. 우선순위 큐의 구현을 고려했을 때, 가장 먼저 나가는 데이터는 우선순위가 가장 높은 루트 노드다.

2. 루트 노드가 삭제되고 난 이후에도 완전 이진 트리의 구조를 유지함과 동시에 우선순위 관계를 유지해야 한다.

 

이 두 가지를 생각하면서 다음의 과정을 수행하면 된다.

1) 현재 트리의 가장 마지막 위치에 있는 노드를 루트 노드의 자리로 옮긴다.

2) 왼쪽과 오른쪽 자식 노드와 우선순위를 비교하여 우선 순위가 높은 노드와 루트 노드를 교환한다.

만약 왼쪽의 우선순위가 더 높다면 왼쪽을, 오른쪽이 더 높다면 오른쪽 노드와 교환한다.

3) 삽입과 마찬가지로 왼쪽과 오른쪽 자식노드와 우선순위를 비교하면서 자신의 위치를 찾을 때까지 반복한다.

 

[그래서 우선순위 큐를 구현하는데 왜 힙이 적합한가?]

우선순위 큐를 배열, 연결 리스트, 힙 기반으로 구현했을 때의 시간 복잡도는 다음과 같게 된다.

1. 배열 기반 우선순위 큐 - 데이터 저장: O(n) / 데이터 삭제: O(1)

2. 연결 리스트 기반 우선순위 큐 - 데이터 저장: O(n) / 데이터 삭제: O(1)

이 둘은 우선순위가 높을수록 배열과 리스트의 앞부분에 배치하는 방식으로 삭제는 굉장히 빠르게 가능하다.

하지만 데이터를 저장하는 데에는 모든 데이터를 순회하는 경우 데이터의 양이 n이라면 n만큼의 시간이 걸린다.

 

그렇다면 힙은?

3. 힙 기반 우선순위 큐 - 데이터 저장: O(log_2n) / 데이터 삭제: O(log_2n)

힙을 기반으로 하면 트리의 높이에 해당하는 수만큼만 비교연산을 진행하면 된다.

이 말은 트리의 높이가 하나 늘어날 때마다 비교 연산의 횟수가 1회 증가한다는 뜻이다.

그리고 힙은 완전 이진 트리라는 특성 상 트리의 높이가 하나 늘어날 때마다 데이터의 양은 2배로 증가한다.

하지만, 데이터 양이 2배 증가해야 비교 연산 횟수가 1회 증가하므로 log_2n의 수행 시간을 가지게 된다.

그래서 수행 속도나 성능 면에서도 힙으로 구현하는 것이 가장 합리적이라고 볼 수 있다.

 

[힙은 배열로 구현한다]

힙은 배열로도, 연결 리스트로도 구현이 가능하다.

하지만 일반적으로 배열로 구현하는 데, 그 이유는 다음과 같다.

"연결 리스트 기반으로 힙을 구현하게 되면 새로운 노드를 삽입할 때 마지막 위치를 추가하는 것이 어렵다."

하지만 배열을 기반으로 하면 인덱스로 접근하기 때문에 마지막 위치에 추가하는 것이 굉장히 용이하다.

그렇기 때문에 배열로 구현하는 것이 일반적이다.

 

[배열 기반의 힙을 구현할 때 인덱스 값을 구하는 방법]

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

오른쪽 자식 노드의 인덱스 값 = (부모 노드의 인덱스 값 * 2) +1

부모 노드의 인덱스 값 = 자식 노드의 인덱스 값 / 2 (여기서 나눠 떨어지는 값은 정수형 나눗셈. 5/2=2.5가 아니라 2)

 

이론적인 부분들은 다 정리를 했고, 나머지 코드 부분에는 주석을 달아놓았으니 그걸 보면서 다시 복습하면 될 것 같다.

솔직히 어렵다기보다는 뭔가 난해했던 자료구조였다.