■ 성능 ▷ MaxHeap을 만들어서 DeleteMax를 반복 수행하여 정렬 ▷ N을 입력 파일의 크기라 하면 BuildHeap O(N), N번 DeleteMax O(NlogN) ▷ BuildHeap은 내부노드(총 N/2개)에서만 수행되면 됨 - 단말노드는더이상내려갈곳이없으므로을적용할필요가없음 - N/2 노드(마지막 내부노드 위치)부터 뿌리 노드까지만 적용되면 됨 - 적용 범위가 반으로 줄었기 때문에 성능면에서 크게 향상된다. O(NlogN) ▷ 이론적으로 이상적인 O(NlogN)이나 실제 수행시간 길다. ▷ 뛰어난 성능을 가지면서도 추가적인 메모리를 필요로 하지 않음 |
