[Heap]33. Bottom-up Heap Construction

목차

1. Merging Two Heaps

2. Bottom-up Heap Construction

 

1. Merging Two Heaps

 

 Heap-sort도 충분히 빠른 수행이 가능한 강력한 방법이지만, heap을 구성하는 시간을 총 O(n)으로 단축할 수 있는 방법이 있습니다. 이는 두개의 node와 하나의 key값이 주어졌을 때, 이를 서로 합치는 Merging Two Heaps를 활용하여 해결할 수 있습니다. 순서는

 

1) 두개의 heap과 1개의 key값을 준비함

2) 1개의 key값을 root로 하고, 나머지 두개의 heap이 subtree가 되는 새로운 node를 만든다

3) root에서 downheap실행, heap의 규칙을 성립시킨다

 

2. Bottom-up Heap Construction

 

 Bottom-up Heap Construction은 heap 생성시, 하나의 root가 있는 heap에 n번 insert하면서 heap을 생성하는 방식이 아닌, 위 그림과 같이 두개의 heap을 합치고, downheap하는 과정을 반복하면서 heap을 생성하는 방법을 말합니다.

 예를 들어보면,

 

 

 Bottom-up Heap Construction을 사용하게 되면, heap을 생성하는데 걸리는 시간을 기존의 O(nlogn)에서 O(n)으로 줄일 수 있습니다. 따라서 Heap-sort 사용시, heap을 구성하는 첫 번째 작업을 빨리 할 수 있도록 도와줍니다.