[Algorithm] C/C++에서 힙(Heap) 구현하기

업데이트(2019.01.19) : 코드 수정 및 검증 코드 추가

C++에서 힙(Heap)을 구현해보자


환경

  • C++


Heap이란?

개념

  • Heap이란 완전 이진 트리의 일종으로 부모 노드와 자식 노드간에 항상 대소관계가 성립하는 자료구조를 의미합니다.
  • 아래의 사진을 보면 부모 노드가 자식 노드보다 항상 크며 이러한 구조를 최대힙(Max Heap)이라고 하고 그 반대를 최소힙(Min Heap)이라고 합니다.
  • 이 때 부모와 자식 노드의 대소관계만 중요하며 형제 노드들간에는 관계가 없습니다.
  • 이렇게 아래처럼 구현하고 위와 같은 속성(부모와 자식간에 대소관계)을 띄기 때문에 최상단 부모인 루트에는 항상 가장 크거나 작은 값이 오며 이를 이용해서 그 유명한 우선 순위 큐(Priority Queue)의 구현이 가능합니다.


구현

공통

  • 완전 이진 트리는 배열로 구현합니다.
  • 구현을 쉽게 하기 위해 배열을 사용할 때 인덱스는 1부터 사용합니다.
  • 특정 노드의 배열 인덱스가 current라고 한다면 부모 노드current / 2를 통해 찾아갈 수 있고 자식 노드current * 2(좌측 자식 노드) 또는 current * 2 + 1(우측 자식 노드)을 통해서 찾아갈 수 있습니다.
  • 현재 노드 인덱스 : current
  • 부모 노드 인덱스 : current / 2
  • 자식 노드들 인덱스 (순서 대로 좌우) : current * 2, current * 2 + 1


삽입

  • 완전 이진 트리 가장 끝에 원소를 추가하고 추가한 부분의 원소와 해당 원소의 부모 노드와 크기를 비교하고 바꿔가면서 위치를 찾습니다.
void push(int data) {

	// 힙의 가장 끝에 데이터 추가
	heap[++heap_count] = data;

	// 아래의 과정은 child를 parent와 비교하면서 알맞은 위치로 하나씩 올리는 부분
	int child = heap_count;
	int parent = child / 2;
	while (child > 1 && heap[parent] < heap[child]) {
		swap(&heap[parent], &heap[child]);
		child = parent;
		parent = child / 2;
	}

}


삭제

  • 힙의 가장 첫번째 원소를 반환하고 첫번째 위치에 힙의 가장 끝 원소를 대입합니다.
  • 첫번째 원소를 자식과 계속 비교하고 값을 바꿔가면서 힙을 재정렬합니다.
  • 이 때, 자식은 왼쪽과 오른쪽 2개가 생기기 때문에 최대힙을 구현하는 경우에는 더 큰 자식과 값을 바꿉니다.(최소힙일 때는 그 반대!)
int pop() {

	// 힙의 가장 첫번째 원소를 반환
	// 힙의 가장 앞만 보고 있다!
	int result = heap[1];

	// 첫번째 원소를 힙의 가장 끝에 원소와 바꾸고
	// 가장 끝은 이제 쓰지 않을 예정이니 heap_count를 내려준다.
	swap(&heap[1], &heap[heap_count]);
	heap_count--;

	// 아래의 과정은 child를 parent와 비교하면서 알맞은 위치로 하나씩 내리는 부분
	int parent = 1;
	int child = parent * 2;
	if (child + 1 <= heap_count) {
		child = (heap[child] > heap[child + 1]) ? child : child + 1;
	}

	while (child <= heap_count && heap[parent] < heap[child]) {
		swap(&heap[parent], &heap[child]);

		parent = child;
		child = child * 2;
		if (child + 1 <= heap_count) {
			child = (heap[child] > heap[child + 1]) ? child : child + 1;
		}
	}

	return result;
}


코드

#include <stdio.h>
#include <stdlib.h>
#include <time.h>

#define HEAP_SIZE 256
#define ARRAY_SIZE 10

// Max Heap 구현
// 구현을 쉽게 하기 위해서 값들은 모두 양수라고 가정!
// 배열에서 값 0은 비어있음을 의미한다고 가정하자!
// heap은 배열의 인덱스가 1부터 시작합니다!

int heap[HEAP_SIZE]; // max heap
int heap_count = 0; // heap의 원소의 갯수를 나타냄과 동시에 배열의 가장 끝 원소를 나타내며 heap의 끝을 나타내기도 합니다.

void swap(int * a, int * b) {
	int tmp = *a; *a = *b; *b = tmp;
}

void init() {
	heap_count = 0;
}

int size() {
	return heap_count;
}

void push(int data) {

	// 힙의 가장 끝에 데이터 추가
	heap[++heap_count] = data;

	// 아래의 과정은 child를 parent와 비교하면서 알맞은 위치로 하나씩 올리는 부분
	int child = heap_count;
	int parent = child / 2;
	while (child > 1 && heap[parent] < heap[child]) {
		swap(&heap[parent], &heap[child]);
		child = parent;
		parent = child / 2;
	}

}

int pop() {

	// 힙의 가장 첫번째 원소를 반환
	// 힙의 가장 앞만 보고 있다!
	int result = heap[1];

	// 첫번째 원소를 힙의 가장 끝에 원소와 바꾸고
	// 가장 끝은 이제 쓰지 않을 예정이니 heap_count를 내려준다.
	swap(&heap[1], &heap[heap_count]);
	heap_count--;

	// 아래의 과정은 child를 parent와 비교하면서 알맞은 위치로 하나씩 내리는 부분
	int parent = 1;
	int child = parent * 2;
	if (child + 1 <= heap_count) {
		child = (heap[child] > heap[child + 1]) ? child : child + 1;
	}

	while (child <= heap_count && heap[parent] < heap[child]) {
		swap(&heap[parent], &heap[child]);

		parent = child;
		child = child * 2;
		if (child + 1 <= heap_count) {
			child = (heap[child] > heap[child + 1]) ? child : child + 1;
		}
	}

	return result;
}

int main() {

	int arr[ARRAY_SIZE];

	// 랜덤함수를 위한 srand와 seed
	srand(time(NULL));

	// 배열 초기화
	for (int i = 0; i < ARRAY_SIZE; i++) {
		// 1 ~ 50까지의 난수 생성
		arr[i] = rand() % 50 + 1;
	}

	// 삽입
	for (int i = 0; i < ARRAY_SIZE; i++) {
		push(arr[i]);
	}

	// pop 하면서 값들 하나씩 확인
	// Max Heap이기 때문에 값들이 내림차순으로 정렬됨 -> Heap Sort
	for (int i = 0; i < ARRAY_SIZE; i++) {
		printf("%d ", pop());
	}
	printf("\n");

	return 0;
}


검증

#include <stdio.h>
#include <stdlib.h>
#include <time.h>
#include <algorithm>
#include <iostream>
#include <functional>

#define HEAP_SIZE 256
#define TOTAL_TEST_CASE 100
#define TEST_ARRAY_SIZE 20

using namespace std;

int heap[HEAP_SIZE];
int heap_count = 0;

void swap(int * a, int * b) {
	int tmp = *a; *a = *b; *b = tmp;
}

void init() {
	heap_count = 0;
}

int size() {
	return heap_count;
}

void push(int data) {

	// 힙의 가장 끝에 데이터 추가
	heap[++heap_count] = data;

	// 아래의 과정은 child를 parent와 비교하면서 알맞은 위치로 하나씩 올리는 부분
	int child = heap_count;
	int parent = child / 2;
	while (child > 1 && heap[parent] < heap[child]) {
		swap(&heap[parent], &heap[child]);
		child = parent;
		parent = child / 2;
	}

}

int pop() {

	// 힙의 가장 첫번째 원소를 반환
	// 힙의 가장 앞만 보고 있다!
	int result = heap[1];

	// 첫번째 원소를 힙의 가장 끝에 원소와 바꾸고
	// 가장 끝은 이제 쓰지 않을 예정이니 heap_count를 내려준다.
	swap(&heap[1], &heap[heap_count]);
	heap_count--;

	// 아래의 과정은 child를 parent와 비교하면서 알맞은 위치로 하나씩 내리는 부분
	int parent = 1;
	int child = parent * 2;
	if (child + 1 <= heap_count) {
		child = (heap[child] > heap[child + 1]) ? child : child + 1;
	}

	while (child <= heap_count && heap[parent] < heap[child]) {
		swap(&heap[parent], &heap[child]);

		parent = child;
		child = child * 2;
		if (child + 1 <= heap_count) {
			child = (heap[child] > heap[child + 1]) ? child : child + 1;
		}
	}

	return result;
}

int main() {

	int arr[TEST_ARRAY_SIZE]; // heap에 이용할 자료들
	int ans_arr[TEST_ARRAY_SIZE]; // 검증에 사용할 자료들

	srand(time(NULL));

	int test_case;
	int correct = 0;

	for (test_case = 1; test_case <= TOTAL_TEST_CASE; ++test_case) {

		// 같은지 확인하는 변수
		bool is_equal = true;

		// 자료들 입력
		for (int i = 0; i < TEST_ARRAY_SIZE; i++) {
			arr[i] = rand() % 2000 + 1; // 1 ~ 2000 사이의 난수 생성
			ans_arr[i] = arr[i];
		}

		// heap 정렬
		for (int i = 0; i < TEST_ARRAY_SIZE; i++) {
			push(arr[i]);
		}
		for (int i = 0; i < TEST_ARRAY_SIZE; i++) {
			arr[i] = pop();
		}

		// 정답 생성
		// greater<int>()는 내림차순을 위해서 사용
		// sort(ans_arr, ans_arr+TEST_ARRAY_SIZE)만 사용하면 오름차순이 됨
		sort(ans_arr, ans_arr + TEST_ARRAY_SIZE, greater<int>());

		// 정답과 힙정렬 결과 비교
		for (int i = 0; i < TEST_ARRAY_SIZE; i++) {
			if (ans_arr[i] != arr[i]) {
				is_equal = false;
				break;
			}
		}

		if (is_equal) correct++;

	}

	printf("Total : %d / %d\n", correct, TOTAL_TEST_CASE);

	return 0;
}


참고자료

[Python] pdb를 이용해 파이썬 코드 디버깅하기

> pdb를 이용해 python 코드를 디버깅하는 방법을 알아보자.## 환경- Linux 기반 시스템- Bash shell(/bin/bash)- Python## pdb### pdb란?- ```pdb``` : 파이썬 디버깅 도구로 파인썬 인터프리터...… Continue reading