[자료구조] Heap에 대하여

1. 힙(Heap)이란?

힙은 완전 이진 트리 기반의 자료구조로, 우선순위 큐를 구현하는데 주로 사용된다.
각 노드는 자식 노드보다 큰(최대 힙) 또는 작은(최소 힙) 값을 가지며, 이러한 특성을 힙 속성(heap property)이라 한다. 힙은 두 가지 주요 유형으로 분류된다.

• 최소 힙(Min-Heap): 각 부모 노드의 값이 자식 노드의 값보다 작거나 같아야 하며, 따라서 루트에는 힙에 있는 최솟값이 위치.
• 최대 힙(Max-Heap): 각 부모 노드의 값이 자식 노드의 값보다 크거나 같아야 하며, 따라서 루트에는 힙에 있는 최대값이 위치.

 

2. 그러면 힙은 왜 사용하지??

일반적인 배열에서 최솟값이나 최댓값을 찾기 위해서는 Ο(n)만큼 시간이 걸린다.
(배열의 길이가 최대 n개이기 떄문에)

하지만 힙을 사용하면 O(1)만큼 소요되므로, 배열을 사용할 때보다 빠르게 최솟값과 최댓값을 구할 수 있다.

(참고로, 일반 배열을 통으로 힙 구조로 변경할 때는 O(N)이 걸리고, 요소 하나하나를 힙 구조로 만들 때에는 O(NlogN)이 걸린다. 이유는 밑에서 설명 ㅎㅎ!!)

결론적으로 힙은 우선순위 큐와 같이 최댓값 또는 최솟값을 빠르게 찾아야 하는 알고리즘 등에 활용된다.

 

3. 힙의 구조와 내부 구현

힙은 완전 이진 트리이며, 주로 배열을 사용하여 구현된다. 완전 이진 트리의 특성상, 힙은 마지막 layer를 제외하고 모든 layer가 완전히 채워져 있으며, 마지막 layer는 왼쪽부터 오른쪽으로 채워진다.

완전 이진 트리 : 이진 트리에 노드를 삽입할 때 왼쪽부터 차례대로 삽입하는 트리이다.

                          아래 그림과 같이 나타내며, 왼쪽이 비어있고 오른쪽이 채워져 있는 형태는 완전 이진 트리가 아니다.

완전 이진 트리 구조

 

 

 

최대힙 기준으로 연산(삽입, 삭제)이 일어날 때의 과정을 살펴보면,

삽입

1. 힙에 새로운 요소가 들어오면, 일단 새로운 노드를 힙의 마지막 노드에 이어서 삽입한다.
2. 새로운 노드를 부모 노드들과 교환해서 힙의 성질을 만족시킨다.

/* 현재 요소의 개수가 heap_size인 힙 h에 item을 삽입한다. */
// 최대 힙(max heap) 삽입 함수
void insert_max_heap(HeapType *h, element item){
  int i;
  i = ++(h->heap_size); // 힙 크기를 하나 증가

  /* 트리를 거슬러 올라가면서 부모 노드와 비교하는 과정 */
  // i가 루트 노트(index: 1)이 아니고, 삽입할 item의 값이 i의 부모 노드(index: i/2)보다 크면
  while((i != 1) && (item.key > h->heap[i/2].key)){
    // i번째 노드와 부모 노드를 교환환다.
    h->heap[i] = h->heap[i/2];
    // 한 레벨 위로 올라단다.
    i /= 2;
  }
  h->heap[i] = item; // 새로운 노드를 삽입
}

 

삭제

1. 최대 힙에서 최댓값은 루트 노드이므로 루트 노드가 삭제된다.
2. 삭제된 루트 노드에는 힙의 마지막 노드를 가져온다.
3. 힙을 재구성한다.

// 최대 힙(max heap) 삭제 함수
element delete_max_heap(HeapType *h){
  int parent, child;
  element item, temp;

  item = h->heap[1]; // 루트 노드 값을 반환하기 위해 item에 할당
  temp = h->heap[(h->heap_size)--]; // 마지막 노드를 temp에 할당하고 힙 크기를 하나 감소
  parent = 1;
  child = 2;

  while(child <= h->heap_size){
    // 현재 노드의 자식 노드 중 더 큰 자식 노드를 찾는다. (루트 노드의 왼쪽 자식 노드(index: 2)부터 비교 시작)
    if( (child < h->heap_size) && ((h->heap[child].key) < h->heap[child+1].key) ){
      child++;
    }
    // 더 큰 자식 노드보다 마지막 노드가 크면, while문 중지
    if( temp.key >= h->heap[child].key ){
      break;
    }

    // 더 큰 자식 노드보다 마지막 노드가 작으면, 부모 노드와 더 큰 자식 노드를 교환
    h->heap[parent] = h->heap[child];
    // 한 단계 아래로 이동
    parent = child;
    child *= 2;
  }

  // 마지막 노드를 재구성한 위치에 삽입
  h->heap[parent] = temp;
  // 최댓값(루트 노드 값)을 반환
  return item;
}

3. 시간 복잡도

• 삽입(heappush): 새 요소가 배열의 끝에 추가되고, 부모 노드와 비교하여 필요한 경우 위치가 조정된다. 이 과정에서의 시간 복잡도는 O(logN)이다. (힙의 속성을 만족하기 위해 최악의 경우 트리의 높이까지 탐색하게 되므로)
• 삭제(heappop): 힙에서는 주로 루트 노드가 삭제된다. 삭제 후, 마지막 요소가 루트로 이동하고, 적절한 위치를 찾을 때까지 아래로 조정된다. 이 과정의 시간 복잡도도 O(logN)이다.
• 정렬(heapify): heapify자체는 O(N). 그러나, 처음부터 요소 하나씩 힙구조로 정렬시키려 하면 O(N logN)이다. (N = 요소의 개수, logN = 삽입연산의 속도)

 

번외)  Heap과 이진 탐색 트리(BST)의 차이점

두 자료구조 모두 완전 이진 트리 구조를 따르지만 몇 가지 차이점이 있다.
BST는 나중에 자세하게 다룰 예정이니 지금은 비슷해 보이는 둘의 차이점만 알고 가자.

 

힙

• 최대 힙의 경우, 각 노드의 값이 자식 노드보다 크거나 같다.
• 힙은 형제 노드의 크기를 상관하지 않는다.
• 최대/최소를 구하는 문제에서 쓰인다.

BST(Binary Search Tree)

• 노드의 크기 순서가 왼쪽 자식 < 부모 < 오른쪽 자식 순이다.
• 위의 규칙을 만족하면서 형제노드끼리도 오른쪽 노드가 왼쪽 노드보다 크다.
• 탐색을 위한 구조이다.