[자료구조] Heap (1)

정의

Heap은 Binary Tree의 일종으로, 다음과 같은 특징을 가진다.

1) Heap-Order: 부모 node의 key와 그 자식 node의 key간 특정한 순서가 존재한다. 부모의 key가 항상 자식의 key보다 큰 경우를 max-heap, 작은 경우를 min-heap 이라 한다. 

 이러한 특성 때문에 heap에서는 항상 가장 큰 key 값을 가진(max-heap의 경우), 또는 가장 작은 key 값을 가진(min-heap의 경우) node가 root node가 된다. 

 

2) Complete Binary Tree

heap은 complete binary tree 구조로, 각 level이 가질 수 있는 최대한의 node를 가지고 있다(1->2->4...). 따라서 n개의 element를 가진 heap의 높이 h는 floor(logn) 이다. 

 

Heap에서의 Insertion 연산

앞서 heap은 부모 노드와 자식 노드의 key 간에 특정한 순서가 있어야 한다고 했다. 따라서 heap에 새로운 element를 추가하면, 이러한 heap의 성질에 부합하도록 node들 간의 관계를 조정해 주어야 한다. 이를 up-heap bubbling이라고 한다.

 

위 그림은 up-heap bubbling의 간단한 예시이다. 원 내의 숫자는 key 값을 의미하고, 이 heap은 최소 key 값을 가진 node가 root가 되는 min-heap이다. 새로운 node를 추가할 때, 가장 먼저 그 노드를 맨 끝에 추가하고, 부모 노드와의 비교를 통해서 해당 heap의 조건을 만족하도록 위치를 바꾸어 준다.

 

앞서 heap은 complete binary tree이고 따라서 높이 h가 floot(n)이라고 했는데, 위 예시와 같이 up-heap bubbling은 최악의 경우에 h step만큼의 연산이 필요하다. 따라서 heap에서의 insertion 연산은 O(h) 만큼의 time complexity를 갖는다.

 

Heap에서의 removal 연산

여기서는 root node를 제거하는 경우를 살펴볼 것이다. heap은 가장 큰/작은 key를 가진 node를 계속 추적하기에 유리한 자료구조이기에 이에 해당하는 root node를 제거해야 하는 경우가 자주 생긴다. 가령, heap을 통해 priority queue를 구현했다면 root node를 참조하거나 반환 후 제거하는 연산을 자주 수행하게 될 것이다.

 

heap에서 root node를 제거하면 heap이 두 개의 subtree로 분할된다. 따라서, 이를 방지하기 위해 먼저 제거할 root node를 가장 끝 노드와 치환한 후에 가장 끝 노드를 제거하고, 다시 heap의 정렬 규칙을 맞추기 위해 부모와 자식 node들을 비교해 가며 교체해 주어야 한다. 이 과정을 down-heap bubbling이라고 한다. 

이 연산도 마찬가지로 최악의 경우 heap 높이만큼의 step이 필요하기 때문에, heap의 removal 연산은 O(h)의 time complexity를 갖는다.