[자료구조] 힙(Heap) 정리

1. 힙(Heap) 이란?

Heap은 완전 이진트리의 한 종류로써, 우선순위 큐(Priority Queue)를 위해 고안된 자료 구조입니다. 특히, 다수의 자료에서 최소값과 최대값을 빠르게 찾을 수 있는 특징을 가지고 있습니다. 

Heap

 

2. Heap의 종류

• 최대 힙(Max Heap)
  최대 힙은 부모 노드의 값이 자식 노드 보다 크거나 같은 경우를 만족하는 완전 이진트리를 말합니다.
  (key(parents node) >= key(child node))
  부모 노드의 값이 항상 자식 노드보다 크거나 같기 때문에, root node는 항상 최대값을 가지게 된다.
• 최소 힙(Min Heap)
  최소 힙은 부모 노드의 값이 자식 보드보다 작거나 같은 경우를 만족하는 완전 이진트리를 말합니다.
  (key(parents node) <= key(child node))
  부모 노드의 값이 항상 자식 노드보다 작거나 같기 때문에, root node는 항상 최소값을 가지게 된다.

3. Heapify

이미 값들이 채워진 완전 이진트리가 있을 때, 새로운 값을 추가하거나 삭제하는 경우에 완전 이진트리의 성질이 깨지는 경우가 존재한다. 이때, 깨진 트리의 값을 다시 맞춰는 작업을 Heapify라고 한다.

 

3.1. Insertion

예를 들어, 최소 힙(Min Heap)이 다음과 같은 상황이라고 가정해봅시다. 보라색 노드는 기존에 있던 힙을 의미하며, 새로운 노드로 1을 추가하는 상황이 발생했습니다.

Insert new node!

 

최소 힙은 부모 노드의 값이 항상 자식 노드보다 작아야 하므로, 아래 파랑색 부분에서 문제가 발생하였습니다.

Problem!

이때 가장 간단한 해결 방법은 부모 노드와 자식 노드를 바꿔주면 됩니다. 즉, 새롭게 들어온 노드(자식 노드)에 대해 부모 노드와 비교하여, 부모 노드가 새로 들어온 자식 노드보다 크거나 같은 경우, 두 노드의 값을 바꿔주는 방법입니다. 이를 Upheap 이라고 합니다.

그림으로 보면 다음과 같습니다.

[1] 새로 들어온 1이 부모 노드인 6보다 작으므로, 두 노드의 값을 바꿔줍니다. 

 

[2] 다시한번 부모 노드와 비교해줍니다. 부모 노드인 2는 1보다 크므로 최소 힙의 조건에 부합하지 않습니다. 따라서 이전 방법과 같은 방법으로 두 값을 바꿔줍니다.

 

새로 들어온 노드인 1이 루트 노드(root node)가 되서야 비로소 조건에 맞는 최소 힙이 되었습니다.

MinHeap: Insert

 

3.2. Removal

이번에는 반대로 삭제하는 경우에 대해서도 생각해보겠습니다. 3.1과 마찬가지로, 다음과 같은 최소 힙이 있다고 가정해봅시다. 최소 힙에서의 삭제는 가장 작은 값을 제거하는 것을 의미합니다(즉, 숫자가 낮을수록 우선순위가 높음을 의미합니다). 따라서, 아래 예시에서 값을 하나 제거 한다는 의미는 root node의 값을 제거 한다는 의미입니다.

Example of Removal from MinHeap

root node를 제거하게 되면, 해당 root node는 아무것도 없게 됩니다. 하지만, root node는 반드시 존재해야 하므로, 어떤 값으로든 채워 넣어야 합니다. 여기서 가장 간단히 생각해볼 수 있는 방법은 완전 이진트리의 마지막 노드(last node)를 먼저 root node로 채우는 방법입니다.

Switch

하지만, leaf node의 값이 root node 로 가게 되면 최소 힙의 조건이 맞지 않게 됩니다. 따라서 이 경우에는 삽입(Insertion)때와 마찬가지로 최소 힙의 조건에 맞게 각 노드의 위치는 바꿔주어야 합니다. 이때도 바꾸는 방법은 삽입과 마찬가지로 부모 노드와 자식 노드의 값을 교환하는 방식을 사용합니다.

 

교환 조건은 부모 노드의 자식 노드를 살펴 보고, 두 자식 노드 중 더 작은 값을 부모 노드와 교환합니다.

 

부모 노드인 7의 자식 노드인 5(left child node)와 6(right child node)를 비교하면 5는 6보다 작으므로, 부모노드(7)과 자식노드(5)를 교환하게 됩니다.

 

교환 이후, 위 방법을 최소 힙이 만족할때까지 반복합니다. 위 예시 같은 경우에는 7의 자식 노드가 9이므로 최소 힙의 조건을 만족하는 완전이진트리가 되었으므로 더이상 바꾸지 않고 종료합니다.

제거 전과 후 비교

4. Python Implementation