[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;
}