[자료구조] Heap(2)

새로운 last node 위치 찾기

앞선 포스팅에서 heap의 insertion, removal 연산이 last node를 필요로 한다는 것을 언급하였다. insertion 연산은 맨 끝에( 새로운 last node 위치에) 새 node를 삽입한 후 up-heap bubbling을 통해 heap을 업데이트하였고, removal 연산은 제거하고자 하는 node를 last node와 교환한 후 down-heap bubbling을 통해 heap을 업데이트하였다.

 

따라서 heap에서는 last node 위치를 적절히 업데이트 해 주는 것이 필수적이다.

 

insertion 연산을 할 때는 다음 절차를 거쳐 새 last node가 삽입될 위치를 구한다.

 

1. 기존 last node로부터, 어떠한 node의 left child 또는 root node가 나올 때까지 거슬러 올라간다.

2. left child/root node를 찾으면, 해당 node의 right sibling 으로 이동한다.(root node까지 거슬러 올라갔을 경우 right child)

3. leaf가 나올 때까지 left child들로 이동한 후, last node를 추가한다.

 

 removal 연산 후에는 다음 절차를 거쳐 last node를 업데이트한다.

 

1. (기존의 지워진) last node가 있던 위치로부터, 어떠한 node의 right child 또는 root node가 나올 때까지 거슬러 올라간다.

2. right child/root node를 찾으면, 해당 node의 left sibling으로 이동한다. (root node까지 거슬러 올라갔을 경우 left child)

3. leaf 에 닿을 때까지 right child로 이동한다. 최종적으로 도착한 node가 새로운 last node가 된다. 

 

Buttom-up Heap Contruction

list가 주어졌을 때, 이 list의 원소들을 heap으로 변경하는 방법에는 먼저 하나씩 element들을 순회해 가며 heap에 추가해 주는 방법이 있다. 앞서 포스팅하였듯, heap에서의 insertion 연산은 O(h)의 time complexity를 가지고 h는 floor(logn)이기 때문에, 이 방법은 O(nlogn)의  time complexity를 갖는다. (O(h)의 insertion 연산을 n번 하므로)

 

또 다른 방법으로는 1/2, 1/4, 1/8 .. 개의 node들을 순서대로 root로 삼고 down-heap bubbling을 통해 병합하여 heap을 구성하는 방법이 있는데, 이 방법이 buttom-up heap construction이다. 

 

먼저 앞의 절반 element들을 root node로 삼는다.

 

다시, 그 다음 절반 element들을 앞서 늘어놓은 root node들의 부모로 삼아 이들을 병합하고, down-heap bubbling을 통해 heap property를 맞춘다.

 

또 다시 그 다음 절반 element들을 사용하여 이 과정을 반복한다. 

 

즉 1) 두 개의 tree를 준비하고, 2) 그 두 tree를 새로 root가 될 node의 subtree로 만들어 결합하고 3) down-heap bubbling을 통해 해당 heap의 특성을 맞추어 주는 것이다. 

 

이 방법을 이용하여 heap을 구성하면 O(n)의 time complexity로 heap을 구성할 수 있어, 앞서 소개한 방법보다(O(nlogn)) 더 효율적이다.

 

Heap sort

앞서 포스팅한 heap의 "부모 node의 key가 항상 자식 node와 일정한 대소관계를 갖는다."는 특성을 활용해 heap을 정렬에 사용할 수 있다. 

 

1. 먼저, 정렬해야 할 list를 complete binary tree 형태로 바꾼다.

 

2. 이후, buttom-up heap construction에서 그랬듯, leaf node부터 down-heap bubbling을 통해 해당 complete binary tree를 heap의 형태로 바꿔 준다.

 

3. root node를 제거하고, 다시 down-heap bubbling을 통해 특성에 맞도록 heap을 정비하는 과정을 반복한다.

 

이 과정을 통해, O(nlogn)의 time complexity로 정렬을 수행할 수 있다.