[자료구조론] C로 힙을 만들어보자

kysung95·2021년 6월 1일
CS자료구조
1

자료구조론

목록 보기
8/11
post-thumbnail

안녕하세요. 김용성입니다. 오늘은 힙에 대해 다뤄볼까 합니다.

히프

영어 'heap'의 뜻은 "더미"입니다. 컴퓨터 분야에서 힙은 완전이진트리 기반의 "더미"와 모습이 비슷한 특정한 자료 구조를 말합니다.
조금 더 자세히 이야기하면 힙은 여러개의 값들 중에서 가장 큰 값이나 가장 작은 값을 빠르게 찾아내도록 만들어진 자료구조입니다. 그림을 한번 살펴보겠습니다.

그림을 살펴보면 루트 노드인 9값이 가장 큰 상황입니다. 그렇지만 그 아래 서브트리들에서는? 부모 노드가 자식 노드보다 값이 크기만 하면 별도의 정렬을 더 하지 않습니다.

즉, 힙 안에서 데이터들은 느슨한 정렬 상태를 유지하는 것이죠. 큰 값이 상위 레벨에 있고 작은 값이 하위 레벨에 있다는 정도만 정렬되어 있으면, 힙의 성질이 유지되는 것입니다. 일일이 모든 요소들에 대해 정렬을 하지 않고 그때 그때 해당 자료형에서 가장 큰 값 혹은, 가장 작은 값을 뽑아내야할 때 더 효율적인 구조가 되겠죠?

✋✋ 그리고 다시 한번 말씀드리지만 힙은 반드시 완전이진트리의 구조를 지니고 있어야 합니다!

힙의 종류

힙에는 두 가지 종류의 힙트리가 존재합니다. 하나는 부모 노드의 키 값이 자식 노드보다 큰 최대 힙(max heap), 또 다른 하나는 반대로 노드의 키 값이 자식 노드보다 작은 최소 힙(min heap) 인데요. 두 가지의 힙은 단지 부등호만 달라지고 나머지는 완전히 동일합니다. 오늘 저는 최대 힙을 다뤄보도록 하겠습니다.

최대 힙
key(부모 노드)>=key(자식 노드)

최소 힙
key(부모 노드)<=key(자식 노드)

힙의 메소드

힙은 완전 이진 트리이기 때문에 각각의 노드에 차례대로 번호를 붙일 수가 있습니다. 이 번호를 배열의 인덱스로 생각하고 힙의 노드들을 쉽게 저장할 수 있죠. 힙을 저장하는 표준적인 자료구조는 배열입니다.

그리고 제가 이전 포스팅에서 언급했던 트리의 성질이죠.

부모의 번호*2=왼쪽 자식의 번호
부모의 번호*2+1=오른쪽 자식의 번호

이 성질을 예외없이 사용하기 위해 편의상 시작 점을 0번 인덱스가 아닌 1번 인덱스라고 정해놓고 시작하도록 하겠습니다.

이제 힙의 기본적인 구조체를 정의해보도록 하겠습니다. 힙 구조체의 멤버로는 heap이라는 이름을 가진 배열과,사이즈를 담은 int 변수가 존재합니다.

//힙 구조체 정의
#define MAX_ELEMENT 200
typedef struct{
    int key;
} element;
typedef struct{
   element heap[MAX_ELEMENT];
   int heap_size;
} HeapType;
//힙 선언
HeapType *heap;

기본적으로 배열을 사용하기 때문에 그렇게 어려운 느낌은 아닙니다.
이제 추상 메소드을 한번 살펴보겠습니다.

insert_max_heap(h,item)
최대 힙에 요소 삽입
delete_max_heap(h)
최대 힙에서 요소 삭제
heap_sort(element a[],int n)

힙은 가장 큰 값에 대한 처리가 중요하다고 했듯이 메소드 자체도 요소 삽입 후 힙을 정리해주는 메소드와 최대 크기 요소를 삭제해주는 메소드가 자주 사용됩니다.

삽입 알고리즘

삽입 알고리즘부터 만들어보겠습니다.
힙트리의 삽입 알고리즘은 다음과 같습니다.

insert_max_heap(A,key):
   heap_size<-heap_size+1; //1
   i<-heap_size; //2
   A[i]<-key; //3
   while i!=1 and A[i]>A[PARENT(i)]do //4
          A[i]<->A[PARENT]; //5
          i<-PARENT(i); //6

동작 과정은 다음과 같습니다.

1- 히프크기 증가
2~3- 증가된 히프 크기 위치에 새로운 노드 삽입
4- i가 루트 노드가 아니고 i번째 노드가 i의 부모 노드보다 크면
5~6- i번째 노드와 부모 노드 교환

어느정도 감이 오시나요? 일단 요소가 삽입이 되면 최하단에 위치시킵니다. 그 이후에 부모 노드와의 비교를 반복하며 만약 삽입된 요소가 부모 노드보다 클 경우 부모 노드와의 위치를 스와핑해주는 것이죠. 힙에서는 형제 노드와의 대소비교는 아무 의미가 없습니다. 오로지 부모 노드와의 비교만 하면 되는 것입니다.

코드로 구현하면 다음과 같습니다.

void insert_max_heap(HeapType *h,element item)
{
  int i;
  i=++(h->heap_size);
  
  while((i!=1)&&(item.key>h->heap[i/2].key)){
     h->heap[i]=h->heap[i/2];
     i/=2;
  }
  h->heap[i]=item;
}

알고리즘과 조금 다르게 구현한 부분이 있습니다. 알고리즘에서는 비교 후 스와핑해주는 과정을 반복하였지만, 코드 구현시에는 삽입될 위치가 확실히 정해진 다음에 최종적으로 새로운 노드의 위치를 정해줍니다. 이렇게 함으로써 이동 횟수를 줄일 수 있기 때문이죠.

삭제 알고리즘

최대힙에서의 삭제 연산은 최대값을 가진 요소를 삭제하는 것입니다. 최대 힙에서의 최대값은 무조건 루트 노드이므로 루트 노드가 삭제됩니다. 루트 노드 삭제 후에도 힙의 성질을 유지할 수 있게끔 재구성하는 것이 필요한데요. 이 부분에 대해 살펴보도록 하겠습니다.

처음에 저는 이해가되지 않았던 것이, 어차피 맨위 루트 노드가 나가면 그 다음 서브트리에 있는 두개의 값 중 하나가 최대값이 되는 것이 아닌가? 하고 생각을 했었는데, 절대 아닙니다. 그 이유는 왼쪽 서브트리의 키값이 오른쪽 서브트리의 키값보다 클 경우 왼쪽 서브트리의 자식 노드가 오른쪽 서브트리 값보다 클 수도 있기 때문이죠. 그렇기 때문에 힙에서는 다음과 같은 방법으로 힙을 재구성해줍니다.


delete_max_heap(A): 
     item<-A[1]; //1
     A[1]<-A[heap_size]; //2
     heap_size<-heap_size-1; //3
     i<-2; //4
     while i<=heap_size do //5
        if i<heap_size and A[i+1]>A[i] //6
           then largest<-i+1; //7
           else largest<-i; //8
        if A[PARENT(largest)]>A[largest] //9
           then break; //10
        A[PARENT(largest)]<->A[largest];//11
        i<-CHILD(largest);
        
    return item;

알고리즘을 보고 다소 의아하신 분들이 있을거예요.
삭제 연산이 이뤄지게 되면 그 이후에는 가장 마지막 요소가 1번 인덱스의 자리로 올라오게 됩니다. 그 이후에는 서브트리의 값중 더 큰 값과 비교를 하며 만약 서브트리의 값이 더 클 경우 위치를 스와핑하게 되죠. 이것이 삭제 연산의 가장 중요한 핵심입니다.

프로세스를 설명하면 다음과 같습니다.

1- 루트 노드 값을 반환하기 위해 item 이라는 변수에 할당
2- 말단 노드를 루트 노드로 이동
3- 힙의 크기를 줄임
4- 루트의 왼쪽 자식(2번 인덱스)부터 비교 시작
5- i가 힙트리의 크기보다 작은동안 반복문 수행
6- 오른쪽 자식이 더 크면
7~8- 두개의 자식 노드 중 큰 값의 인덱스를 largest로 이동
9- largest의 부모 노드가 largest보다 클 경우
10- break
11- 그렇지 않으면 largest와 부모노드를 교환

코드로 구현해보도록 하겠습니다.

element delete_max_heap(HeapType* h)
{
  int parent, child;
  element item, temp;
  
  item=h->heap[1];
  temp=h->heap[(h->heap_size)--];
  parent=1;
  child=2;
  while(child<=h->heap_size){
    if((child<h->heap_size)&&
       (h->heap[child].key)<h->heap[child+1].key)
       child++;
    if(temp.key >= h->heap[child].key) break;
    
    h->heap[parent]=h->heap[child];
    parent=child;
    child*=2;
  }
  h->heap[parent]=temp;
  return item;
}

정렬 알고리즘

힙 정렬 같은 경우에는 nlog2n(2는 밑입니다.)이라는 시간복잡도를 가지고 있습니다. 일반 정렬(n^2)에 비해 효율성이 높다는 장점을 가지고 있죠.

heap_sort 코드는 다음과 같습니다.

void heap_sort(element a[], int n){
  int i;
  HeapType* h;
  
  h=create();
  init(h);
  for(i=0;i<n;i++){
     insert_max_heap(h,a[i]);
  }
  for (i=(n-1);i>=0;i--){
     a[i]=delete_max_heap(h);
  }
  free(h);
}

힙 최종 코드

위에서 구현한 코드들을 통해서 간단하게 힙을 구현해보고 테스트해보도록 하겠습니다.
10,5,30이라는 값을 insert_max_heap 함수를 통해 힙에 넣어준 뒤에 delete_max_heap 함수를 통해 출력해준 뒤 확인해보는 코드입니다.



#include <stdio.h>
#include <stdlib.h>
#define MAX_ELEMENT 200
typedef struct{
  int key;
} element;
typedef struct{
  element heap[MAX_ELEMENT];
  int heap_size;
} HeapType;


HeapType* create()
{
  return (HeapType*)malloc(sizeof(HeapType));
}

void init(HeapType* h)
{
  h->heap_size=0;
}

void insert_max_heap(HeapType *h,element item)
{
  int i;
  i=++(h->heap_size);
  
  while((i!=1)&&(item.key>h->heap[i/2].key)){
     h->heap[i]=h->heap[i/2];
     i/=2;
  }
  h->heap[i]=item;
}


element delete_max_heap(HeapType* h)
{
  int parent, child;
  element item, temp;
  
  item=h->heap[1];
  temp=h->heap[(h->heap_size)--];
  parent=1;
  child=2;
  while(child<=h->heap_size){
    if((child<h->heap_size)&&
       (h->heap[child].key)<h->heap[child+1].key)
       child++;
    if(temp.key >= h->heap[child].key) break;
    
    h->heap[parent]=h->heap[child];
    parent=child;
    child*=2;
  }
  h->heap[parent]=temp;
  return item;
}

int main(void)
{ 
  element e1={10},e2={5},e3={30};
  element e4,e5,e6;
  
  HeapType* heap;
  
  heap=create();
  init(heap);
  
  insert_max_heap(heap,e1);
  insert_max_heap(heap,e2);
  insert_max_heap(heap,e3);
  
  e4=delete_max_heap(heap);
  printf("<%d>",e4.key);
  e5=delete_max_heap(heap);
  printf("<%d>",e5.key);  
  e6=delete_max_heap(heap);
  printf("<%d>",e6.key);

처음에 3개의 요소가 힙에 들어가게 되면 힙의 형태는 루트노드 30 그리고 왼쪽 서브트리에 5라는 값과 오른쪽 서브트리에 10이라는 값이 할당될 것입니다. (5가 먼저 포함되었고 형제끼리의 대소비교는 하지 않기 때문이죠.)

그러나 delete를 차례대로 해줄 시 그때 그때 최대값을 출력해주게 되므로 실행 결과는 다음과 같습니다.

출력 결과
<30> <10> <5>

마무리

프로그래머스-힙

오늘은 힙에 대해 알아보았는데요. 프로그래머스의 힙 문제들이 상당히 힙의 개념을 이해하기 좋게 잘 나와있다고 생각해요. deque를 사용해서 풀어도 되지만 힙을 통해 풀면 훨씬 간단한(?) 그런 문제들이 나와있어서 한번 풀어보시길 추천드리며 링크 달아놓겠습니다.
오늘도 포스팅 읽어주셔서 감사합니다:)

profile
kysung95
김용성입니다.
이전 포스트

[자료구조론] 이진 트리의 순회

다음 포스트

[자료구조론] C로 그래프를 만들자

0개의 댓글