Briefly compare the two heap-construction algorithms

Make heap : bottom up, O(n), off-line algorithm, heapsort에 유용

Heap insert : top-down, O(nlogn), on-line algorithm, priority queue에 유용

 

Make heap은 shift_down을 사용하고 Heap insert(construct heap)은 insert_hep을 사용한다.

shift_down은 구성된 ECBT에서 하위 서브트리부터 순서를 재조정하여 Heap을 구성하는 함수이고, insert_heap은 ECBT를 구성 해 가며 노드를 하나씩 추가해 나가는 것이다.

 

sorting을 목적으로 할 경우 Make heap은 주어진 키값으로 ECBT를 구성 해 놓은 후 순서를 맞추기 때문에 새로운 값이 갑자기 추가되면 모든 과정을 새로 밟아야 한다. 이런 경우를 off-line이라고 한다. Heap insert는 어짜피 키 값을 하나씩 추가 해 가며 Heap을 구성하므로 중간에 키가 추가 되더라도 아무런 문제가 없다. 이런 경우를 on-line이라고 한다.

 

즉, 속도는 Make heap이 더 빠르지만, 새로운 값이 추가될 수 있는 경우를 따지면 Make heap이 더 우수한 알고리즘이라고는 할 수 없다.

 

Make heap은 고정된 키값들을 sorting하는데 유용하고, Heap insert는 키값이 유동적으로 변경되는 priority queue를 구성하는데 유용하다.