[6] Heap

이 글에서는 힙 자료구조에 대해서 알아보도록 하겠습니다.

 

Heap은 최댓값 및 최솟값을 빠르게 찾아내기 위해 고안되었고

완전이진트리를 기본으로 한 자료구조입니다. 

 

우선 완전 이진트리 (complete binary tree)의 속성을 모두 충족합니다. 

완전 이진트리란 트리의 왼쪽부터 비는 곳 없이 채워져 있게 됩니다. 

트리의 유형 설명 (출처 : https://towardsdatascience.com/5-types-of-binary-tree-with-cool-illustrations-9b335c430254?gi=e0c7ff97779b)

위 이미지에서 complete 에 해당하는 구조가 완전 이진트리인데요 (물론 Perfect Binary Tree도 complete에 포함됩니다)

왼쪽부터 노드가 채워지고 중간에 비는 구조가 없는 것을 확인할 수 있습니다. 

 

이런 완전이진 트리의 특성에 하나의 제약 조건을 추가하여 heap 자료구조가 구성됩니다. 

그 특성은 바로 모든 Parent는 자신의 Child보다 크거나 작다는 특성입니다. 

만약 Parent가 Child 보다 크면 이는 Max Heap 이 되는 것이고

Parent가 Child보다 작으면 이는 Min Heap가 되는 것입니다. 

max heap의 예시 (출처 : https://en.wikipedia.org/wiki/Heap_(data_structure))

위 이미지는 Max Heap의 예시인데요

children 간 규칙 없이, parent가 children보다 크다는 규칙이 있습니다.  

 

트리에서 Root에 해당하는 부분이 가장 작거나 큰 구조이고

이를 유지함으로써 heap 자료구조를 구성할 수 있습니다. 

이러한 특성 때문에 heap은 우선순위 큐 (priority queue) 로서의 역할을 하게 됩니다. 

 

우선순위 큐는 큐에 우선순위가 있어, 입력한 순서가 아닌 우선순위에 의해 pop되는 순서가 결정이 되야 하는데

heap 자료구조를 사용하게 되면, 자연스럽게 Root에 해당하는 값이 가장 작거나 큰 것이 되므로

우선순위 큐의 기능을 쉽게 구성할 수 있습니다.

 

Methods

제공되는 메소드는 다양하게 구성할 수 있지만

대표적으로 pop과 push가 있습니다. 

- pop : heap에서 맨 앞에있는 요소를 리턴하고 제거함

- push : heap에 값을 넣음

 

고정 크기 배열로 구현된 heap 에서 시간 복잡도는 pop과 push 모두 worst-case가 log(n)으로 동일합니다. 

위치를 재조정하는 과정에서 최대 트리의 높이만큼 연산이 이루어지는데, 그 크기가 log(n)이기 때문입니다. 

 

Heap은 그 구현 방식에 따라 종류가 다양하고, 그에 따른 서로 다른 시간 복잡도를 지닙니다. 

 

heap의 시간 복잡도 (출처 : https://en.wikipedia.org/wiki/Heap_(data_structure))

Implementation

구현은 배열 혹은 링크드 리스트로 할 수 있지만, 여기서는 간단하게 배열로 max-heap을 구성해보았습니다. 

 

createHeap

typedef struct t_Heap {
  int * arr;
  int size;
  int maxSize;
} Heap;

Heap * createHeap(int size){
  Heap *newHeap = (Heap *)malloc(sizeof(Heap));
  if(newHeap == NULL){
    printf("Failed to allocate memory on heap\n");
    return NULL;
  }

  int *arr = (int *)malloc(sizeof(int) * size + 1);
  if(arr == NULL){
    printf("Failed to allocate memory on array\n");
    return NULL;
  }

  newHeap->arr = arr;
  newHeap->maxSize = size;
  newHeap->size = 0;

  return newHeap;
};

Heap 구조체를 선언하고 이를 초기화하는 함수입니다. 

 

push

void push(Heap *heap, int data){
  heap->arr[++heap->size] = data;

  int child = heap->size;
  int parent = child / 2;

  while(child > 1 && heap->arr[parent] < heap->arr[child]){ // 
    swap(&heap->arr[parent], &heap->arr[child]);
    child = parent;
    parent = child/2;
  }
};

Heap 에 값을 넣는 함수입니다.

계산을 편하게 하기 위해서 인덱스를 1부터 시작하게 두었습니다.

우선 인덱스의 가장 끝부분에 값을 넣은 다음,

parent와 비교하여 parent보다 작을 때 까지 값을 교체합니다. 

여기서 부등호 방향이 반대로 바뀌면 min-heap이 됩니다. 

 

pop

int pop(Heap *heap){
  int ret = heap->arr[1];

  swap(&heap->arr[1], &heap->arr[heap->size]);
  heap->size--;

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

  while(child < heap->size && heap->arr[parent] < heap->arr[child]){
    swap(&heap->arr[parent], &heap->arr[child]);
    
    parent = child;
    child = child * 2;

    if(child + 1 <= heap->maxSize){
      child = (heap->arr[child] > heap->arr[child + 1]) ? child : child + 1;
    }
  }

  return ret;
}

Heap에서 값을 빼는 함수입니다. 

맨 앞에있는 값을 리턴하기 위해 먼저 참조한 후 

맨 뒤에있는 값과 바꾼 후 heap에서 배제하기 위해 Size를 하나 줄입니다. 

 

현재 맨 앞에있는 값이 heap을 만족시킬수 있게 child들 중 큰 녀석과 비교하여 위치를 변경합니다. 

 

#include "heap.h"

int main()
{
  Heap *myHeap = createHeap(100);

  int data[7] = {100, 47, 13, 5, 10, 66, 35};

  for (int i = 0; i < 7; i++)
    push(myHeap, data[i]);

  for (int i = 0; i < 7; i++)
    printf("%d ", pop(myHeap));

  return 0;
}

구현한 Heap을 실행하는 코드입니다. 

위와 같은 순서로 heap에 입력한 후, 하나씩 순차적으로 뺐을때의 결과는 다음과 같습니다. 

 

예상대로 큰 순서대로 정렬되어 나타나는 것을 확인할 수 있습니다.

Heap-Sort는 결국 힙에 요소를 넣고 빼면 자동으로 수행되는 것임을 알 수 있습니다. 

 

Reference

Wikipedia