[Heap]30. Heap-Sort(힙 정렬)

목차

1. Heap-Sort(힙 정렬)

2. 기존 PQ Sorting과 비교

 

1. Heap-Sort(힙 정렬)

 Heap을 활용한 sort은 다음과 같은 특징을 지닙니다.

1) 소요되는 메모리 양은 O(n)

2) insert, removeMin()은 O(logn)의 시간 소모

3) size, empty, min은 O(1)의 시간 소요

 

이때, insert과 removeMin에 O(logn)의 시간이 소모되므로, n개의 임의의 순서로 이루어져있는 배열을 정렬할 시, O(nlogn)의 시간만에 heap을 생성할 수 있습니다.

 

2. 기존 PQ Sorting과 비교

 

 기존의 PQ Sorting을 사용할 시, Selection Sort 혹은 Insertion Sort은 Sorting에 O(n^2)의 시간이 소모되었습니다. 반면 Heap-Sort을 사용할 시, 시간을 O(nlogn)으로 단축할 수 있다는 매우 큰 장점을 지니고 있습니다.