Donghee

Algorithm 232 by J.W.J Williams

HeapSorting은 O(nlogn) sorting algothms(merge, quick, heap)중 가장 느리다. 대신 MergeSorting 과 QuickSorting algothms과 다르게 적은 recursion과 적은 공간을 사용하기 때문에 많은양(몇백만?)이상의 데이터를 sorting 하는데 탁월 하다. 특히 요즘은 많은 양의 데이터를 다르기 때문에 적당하다. resources를 적게 먹기 때문에 user-level application 이나 느린 machine에 사용하기 적당하다.

HeapSorting의 구현은 크게 2개의 부분으로 나눈다. 하나는 HeapTree구조를 만드는것이고, 나머지는 각 요소의 Data를 sorting 하기 위해서 이다.

Programming Pearls 를 보니깐 HeapSorting의 구현은 다른 Sort 방법보다 간단하긴 한데 bentley는 자기가 구현하면 소스가 맘에 들지 않는 모양이다.

floyd의 Tree Sort J.W.J wiliams의 Heap Sort

http://www.aihorizon.com/essays/basiccs/trees/heap.htm

heapsort에 대해서