이진 힙을 사용하는 정렬이다.
-
힙 : 각 묶음에서 큰 수가 위에 오는 형태
-
상단의 힙에 변화가 생기면 하단의 힙에도 영향이 생긴다
-
initial heap으로 만들고,
-
가장 상위 수를 제거하고(가장 큰 수이므로),
-
가장 끝 수를 가장 상위에 넣은 후, 힙을 재정렬한다.
-
위의 경우 가장 상위 수인 77을 제거하고 가장 끝의 수인 5를 77의 자리에 넣는다.
-
방법 1. 데이터를 1씩 추가하며 힙 구성하기
-
방법 2. 입력된 데이터로 힙 구성하기
-> 가장 상단의 수 77을 결과에 추가한다.
-> 가장 끝의 5를 77의 자리에 넣는다.
-> initial heap으로 만든 후 가장 상단의 61을 결과에 추가한다.
-> 가장 끝의 1을 61의 자리에 넣는다.
-> initial heap으로 만든 후 가장 상단의 59를 결과에 추가한다.
-> 가장 끝의 5를 59의 자리에 넣는다.
복잡도
- 하나의 데이터가 힙을 찾아가는 시간 (adjust) : O(log n)
- 전체 시간 : nlogn
- 시간 복잡도 : O(nlogn)
