[자료구조] 힙 (Heap) C/C++ 구현 - 알고리즘 // 최소 힙, 최대 힙

요즘 heap (min heap, max heap) 관련 과제 요청이 많이 들어와서 힙 자료구조에 대해 글을 써봅니다.

힙은 이진트리 (Binary Tree)로 구성할 수 있으며 트리 구조체로 구현하거나 또는 1차원 배열로 쉽게 구현할 수 있습니다.

구현 시 하나의 규칙만 지켜주면 되는데 최소 힙은(min heap) 부모가 자식보다 값이 작아야 하며 최대 힙은 (max heap) 그 반대입니다.

최소 힙과 최대 힙 예시

이진트리의 형태를 띄고있어 루트 노드를 1번 정점이라고 한다면, 자식 노드는 각각 2, 3 번 노드가 됩니다.

여기서 알 수 있는건 부모 정점의 번호가 n이라면 왼쪽 자식의 번호는 2*n, 오른쪽 자식의 번호는 2*n + 1 의 규칙을 띄고있습니다.

노드 번호를 배열의 인덱스로 한다면 아래와 같이 1차원 배열로 표현 가능합니다.

배열의 인덱스를 노드의 번호로 한다면?

그럼 이와 같은 인덱스 규칙과 힙의 성질을 만족하면서 데이터를 넣어보도록 하겠습니다. (MAX heap 기준 설명)

먼저 힙을 구조체로 나타내면 아래 코드와 같습니다.

#define MAX_SIZE (100000)

typedef struct _heap {
	int data[MAX_SIZE];
	int heap_size;
}heap;

// 힙 초기화 함수
heap* init(heap* h) {
	h = (heap*)malloc(sizeof(heap));
	h->heap_size = 0;
	return h;
}

힙은 완전 이진트리의 형태로 데이터를 삽입하기 때문에 새로운 데이터는 가장 마지막 인덱스에 저장되어 루트까지 올라가면서 자신의 위치를 찾습니다.

void add(heap* h, int data) {
	
	// 맨마지막에 넣어준다.
	h->heap_size += 1;
	h->data[h->heap_size] = data;

	// 항상 내 부모의 인덱스는 내 인덱스를 2로 나눈 몫을 취한다.
	int me = h->heap_size;
	int parent = me / 2;

	// 루트까지 올라갈 수 있으므로 부모의 인덱스번호가 1이상이다.
	while (parent) {
		// 부모가 나보다 값이 작으므로 내가 부모위치로 가야한다.
		if (h->data[parent] < h->data[me]) {
			int temp = h->data[parent];
			h->data[parent] = h->data[me];
			h->data[me] = temp;
            
            // 내 위치를 부모로 바꿔주고 새로운 부모 인덱스를 가져온다.
			me = parent;
			parent = me / 2;
		}
        // 만약 부모가 더 크다면 종료.
        else {
			break;
		}
	}
	return;
}

위의 코드를 아래와 같이 실행시켜보면 결과값은 23 9 1 3 5 가 출력되며 아래 그래프처럼 구성됨을 알 수 있다.

int main() {
	heap* h = NULL;
	h = init(h);

	add(h, 3);
	add(h, 5);
	add(h, 1);
	add(h, 23);
	add(h, 9);

	for (int i = 1; i <= h->heap_size; i++) {
		printf("%d ", h->data[i]);
	}
}

삽입 결과.

힙에 데이터를 넣었으니 삭제를 알아보겠습니다.

MAX heap에서 삭제는 가장 큰 값을 반환하고 그 값을 힙에서 제거합니다. 이 후, 가장 마지막에 있는 값을 맨 위로 올린 다음, 아래로 내려가면서 자리를 찾아갑니다. 아래로 내려갈 때, 왼쪽과 오른쪽 자식 중 큰 값과 비교를 합니다. 이는 내 자식의 인덱스 번호가 전체 heap 크기 이하이거나 내가 자식보다 작을 때까지 반복합니다.

삭제 과정.

int empty(heap* h) {
	// 힙 사이즈가 0이면 1 반환, 그 외 0 반환
	return (h->heap_size ? 0 : 1);
}

int remove(heap* h) {
	
	// 가장 큰값을 res 에 저장
	int res = h->data[1];
	// 맨 마지막 데이터를 맨위로 올린다음
	h->data[1] = h->data[h->heap_size];
	// 크기를 1 감소시킴
	h->heap_size -= 1;

	int me = 1;
	int child = 2;
	// 자식의 인덱스가 힙 크기보다 작거나 같으면 반복
	while (child <= h->heap_size) {

		// 오른쪽 자식의 인덱스번호가 힙 크기 이하이면서 왼쪽 자식보다 더 큰경우
		if (child + 1 <= h->heap_size && h->data[child] < h->data[child + 1]) {
			// 비교할 자식의 인덱스를 오른쪽으로 바꿔줌
			child += 1;
		}

		// 나보다 내 자식이 더크다면 값을 바꿔주고 
		if (h->data[me] < h->data[child]) {
			int temp = h->data[me];
			h->data[me] = h->data[child];
			h->data[child] = temp;

			// 내 위치를 바꾼 인덱스위치로 
			me = child;
			child = me * 2;
		}
		// 내가 더 크다면 자리를 찾았으므로 종료.
		else {
			break;
		}
	}
	return res;
}

 

아래의 코드를 돌려보면 결과는 23 9 5 3 1 이 나오게 됩니다. 

int main() {
	heap* h = NULL;
	h = init(h);

	add(h, 3);
	add(h, 5);
	add(h, 1);
	add(h, 23);
	add(h, 9);

	while (!empty(h)) {
		printf("%d ", remove(h));
	}
}

 

MIN heap은 부등호만 반대로 해주면 됩니다.

궁금한 점은 댓글에 남겨주세요~

전체 코드

#include <stdio.h>

#define MAX_SIZE (100000)

typedef struct _heap {
	int data[MAX_SIZE];
	int heap_size;
}heap;

heap* init(heap* h) {
	h = (heap*)malloc(sizeof(heap));
	h->heap_size = 0;
	return h;
}
void add(heap* h, int data) {
	
	// 맨마지막에 넣어준다.
	h->heap_size += 1;
	h->data[h->heap_size] = data;

	int me = h->heap_size;
	int parent = me / 2;

	// 루트까지 올라갈 수 있으므로 부모의 인덱스번호가 1이상이다.
	while (parent) {
		// 부모가 나보다 값이 작으므로 내가 부모위치로 가야한다.
		if (h->data[parent] < h->data[me]) {
			int temp = h->data[parent];
			h->data[parent] = h->data[me];
			h->data[me] = temp;

			me = parent;
			parent = me / 2;
		}
		else {
			break;
		}
	}
	return;
}

int empty(heap* h) {
	// 힙 사이즈가 0이면 1 반환, 그 외 0 반환
	return (h->heap_size ? 0 : 1);
}
int remove(heap* h) {
	
	// 가장 큰값을 res 에 저장
	int res = h->data[1];
	// 맨 마지막 데이터를 맨위로 올린다음
	h->data[1] = h->data[h->heap_size];
	// 크기를 1 감소시킴
	h->heap_size -= 1;

	int me = 1;
	int child = 2;
	// 자식의 인덱스가 힙 크기보다 작거나 같으면 반복
	while (child <= h->heap_size) {

		// 오른쪽 자식의 인덱스번호가 힙 크기 이하이면서 왼쪽 자식보다 더 큰경우
		if (child + 1 <= h->heap_size && h->data[child] < h->data[child + 1]) {
			// 비교할 자식의 인덱스를 오른쪽으로 바꿔줌
			child += 1;
		}

		// 나보다 내 자식이 더크다면 값을 바꿔주고 
		if (h->data[me] < h->data[child]) {
			int temp = h->data[me];
			h->data[me] = h->data[child];
			h->data[child] = temp;

			// 내 위치를 바꾼 인덱스위치로 
			me = child;
			child = me * 2;
		}
		// 내가 더 크다면 자리를 찾았으므로 종료.
		else {
			break;
		}
	}
	return res;
}

int main() {
	heap* h = NULL;
	h = init(h);

	add(h, 3);
	add(h, 5);
	add(h, 1);
	add(h, 23);
	add(h, 9);

	while (!empty(h)) {
		printf("%d ", remove(h));
	}
}