Heap 자료구조 알아보기

힙 자료구조를 이해하기 위해서는 트리, 이진트리, 완전 이진트리에 대한 선행지식을 필요로 합니다.

 

트리는 모든 구성요소가 연결되어 있으며(단일 컴포넌트), 방향을 무시했을 때 사이클이 생기지 않고, 간선 개수가 정점 개수보다 1개 작은 비선형 자료구조를 말합니다.

이진트리는 부모 노드가 최대 2개의 자식을 가지는 자료구조입니다.

 

Full Binary Tree (포화 이진 트리) 

 

먼저 힙을 이해하기 위해 필수적인 내용은 아니지만 차이를 통해 완전 이진트리를 이해하기 위해 포화 이진트리부터 알아보겠습니다.

이진 트리로서 모든 노드가 0개 혹은 2개의 자식을 가지는 이진트리를 말합니다.

    1
   / \
  2   3
 / \ / \
4  5 6  7

    1
   / \
  2   3
 / \ 
4  5 

따라서 다음과 같은 형태들은 포화 이진 트리입니다. 리프노드는 모두 자식이 0개이고, 부모 노드들은 모두 2개의 자식을 가지고 있는 형태이기 때문입니다.

    1
   / \
  2   3
 / \ /
4  5 6

하지만 다음과 같은 형태는 3번 노드가 자식이 1개이므로 포화 이진 트리의 조건에 위배됩니다.

 

Complete Binary Tree (완전 이진 트리)

이진 트리로서 마지막 레벨을 제외한 모든 노드가 채워져 있고, 마지막 레벨의 왼쪽 요소들이 채워져 있는 트리를 말합니다.

    1
   / \
  2   3
 / \ / \
4  5 6  7

    1
   / \
  2   3
 /
4

따라서 다음과 같은 형태는 완전 이진트리입니다. 마지막 레벨을 재외한 모든 노드들은 채워져 있으며, 마지막 레벨의 왼쪽 요소부터 채워져 있기 때문입니다.

    1
   /
  2
 / \ 
3  4

하지만 다음과 같은 형태는 레벨 1에 해당하는 요소가 채워져 있지 않기 때문에 완전 이진트리의 조건에 위배됩니다.

  1
 / \
2   3
   / \
  4   5

해당 형태도 최종 레벨을 제외하고 요소들이 채워져 있지만 최종 레벨의 왼쪽 요소가 비워져 있다는 점에서 완전 이진트리의 조건에 위배됩니다.

 

Heap 자료구조

힙 자료구조는 트리 기반 자료구조로 완전 이진 트리이고 최소 힙 또는 최대 힙의 속성을 따릅니다.

최소 힙

최소 힙은 부모 노드 값은 자식 값보다 작거나 같은 것을 말합니다.

    1
   / \
  2   3
 / \ / \
4  5 6  7

해당 형태는 모든 부모가 자식 이하이므로 최소 힙을 만족합니다. 최소 힙은 당연히 루트 노드의 값이 최소이며 자식으로 갈수록 값이 커지는 것을 확인할 수 있습니다.

    1
   / \
  2   30
 / \  / \
4  5 60  70

해당 조건은 부모보다 자식이 크면 되는 것이므로 해당 트리도 최소 힙입니다. 노드의 레벨로서 구분되는 것이 아님을 유의합니다.

 

최대 힙

최대 힙은 최소힙의 반대입니다. 모든 부모가 자식 노드의 값 이상을 가지는 형태를 말합니다.

    9
   / \
  8   7
 / \ / \
6  5 4  3

해당 형태는 모든 부모가 자식 이상의 값을 가지므로 최대 힙을 만족합니다.

Insert

힙의 삽입 연산은 삽입이 이루어지는 것에 따라 최소 힙, 최대 힙 구조와 완전 이진트리를 유지하는 것이 핵심입니다.

최소 힙을 기준으로 40, 31, 34, 9노드를 추가해 보는 것을 진행해보겠습니다.

40

최초의 루트 노드는 다음과 같이 추가됩니다.

  40
 /
31   

다음으로 완전 이진트리의 조건으로 31을 왼쪽 자식에 추가하였을때, 31은 부모인 40보다 작기 때문에

  31
 /
40   

다음과 같이 노드를 교환하게 되는데 이를 버블링이라고 합니다.

  31
 /  \
40   34

다음으로 34를 오른쪽 자식에 추가하였을때, 부모인 31이 34보다 작기 떄문에 버블링은 필요하지 않습니다.

    31
   /  \
  40   34
 /
9 

    31
   /  \
  9   34
 /
40 


    9
   /  \
  31   34
 /
40 

다음으로 9를 추가하였을 때, 다음과 같이 부모인 40, 그 부모보다도 작으니 31과도 버블링이 총 2번 일어나게 됩니다.

이렇게 힙의 삽입과정에 대해 알아보았는데요, 부모는 항상 자식보다 작으므로 형제간의 비교는 필요하지 않습니다.
삽입 과정에서는 최대 루트 노드까지의 버블링이 필요하므로 시간 복잡도는 O(log n)이 됩니다.

Delete

힙에서 자료를 삭제하는 것은 기본적으로 정렬된 자료에서 값을 뽑아내는 것에 의미가 있으므로 최대 힙에서는 최댓값, 최소 힙에서는 최소값이 삭제되게 됩니다.
그리고 그것은 루트라는 것을 알 수 있습니다.

    9
   / \
  11  10
 / \  / \
40 31 85 34

다음과 같이 최소 힙이 존재할 때 삭제과정을 살펴보도록 하겠습니다.

   / \
  11  10
 / \  / \
40 31 85 34

먼저 다음과 같이 루트가 제거됩니다.

    34
   /  \
  11   10
 / \  /
40 31 85 

다음으로는 완전 이진트리의 조건을 만족하기 위해 최대 레벨의 가장 오른쪽 리프노드가 루트로 승격됩니다.

    10
   /  \
  11   34
 / \  /
40 31 85 

다음으로는 최소 힙을 만족시키기 위해 34의 자식인 11과 10중 가장 작은 값인 10과 버블링을 수행합니다.
이후 새롭게 자식이 된 85와 값을 비교하고, 버블링이 필요하지 않으니 삭제 과정을 마무리합니다.

   /  \
  11   34
 / \  /
40 31 85 

    85
   /  \
  11   34
 / \ 
40 31

    11
   /  \
  85   34
 / \ 
40 31

    11
   /  \
  31   34
 / \ 
40 85

한번 더 노드를 삭제했을 경우 다음과 같이 버블링이 총 2번 발생하는 것을 확인할 수 있습니다.
따라서 힙 자료구조의 루트 노드의 삭제 연산의 시간 복잡도는 삽입과 같이 O(log n) 입니다.

그렇다면 루트 노드가 아닌 특정 노드를 삭제하는 연산의 시간복잡도는 어떻게 될까요. 예를 들어 31을 삭제하는 것을 진행해보겠습니다.

    11
   /  \
 (31)  34
 / \ 
40 85

먼저 31을 찾아야 하는데 탐색에는 당연히 모든 노드를 순회해야 하므로 최대 O(n) 이 소요됩니다.

    11
   /  \
       34
 / \ 
40 85

    11
   /  \
  40   34
   \ 
   85

    11
   /  \
  40   34
 / 
85

이후 다음과 같이 노드를 삭제하고, 최소 힙, 완전 이진트리의 조건을 만족시키는데 추가적으로 O(log n) 시간이 들게 됩니다.
따라서 루트 노드를 제외한 특정 노드의 삭제 연산의 시간 복잡도는 O(n + log n) -> O(n) 이 되게 됩니다.
이는 효율적이지 않다는 것을 파악할 수 있고, 힙 자료구조는 최대값, 최소값을 활용하는 것에 시간 복잡도면에서 유리하다는 것을 알 수 있습니다.

힙과 우선순위 큐

다음으로 알아볼 내용은 힙의 대표적인 활용인 우선순위 큐입니다.

큐는 선형 FIFO 자료구조로서 PushBack(e), PopFront() 연산을 지원하는데요, 우선순위 큐에서는 대기열에 시작과 개념이 우선순위로 대체된다고 생각하시면 됩니다.

즉 우선순위 큐에는 요소를 추가할 수 있고, PopFront() 에 대해서 가장 우선순위가 높은 요소가 삭제되는 것이고, PushBack()는 우선순위 큐에 요소를 추가하는 것입니다.

내용만 봐도 힙은 최소, 최대 힙을 통해 가장 우선순위가 높은 값에 대해 해당 연산을 지원할 수 있기 때문에 힙은 우선순위 큐로 많이 활용되게 됩니다.

이러한 우선순위 큐는 Heap sort 및 Dijkstra, Prim, Huffman Coding 알고리즘에 활용할 수 있습니다.

 

블로그에 올리는 내용은 아래 깃허브에도 정리하고 있습니다.

https://github.com/middlefitting/ComputerScience-roadmap.sh

GitHub - middlefitting/ComputerScience-roadmap.sh

 

참고 자료

 

https://roadmap.sh/computer-science

Computer Science Roadmap: Curriculum for the self taught developer