힙 자료구조를 활용해서 정렬하는 알고리즘
힙 자료구조는 우선순위가 가장 높은 요소가 맨 위 루트노드로 온다.
이를 배열로 구현하면 가장 앞 인덱스의 요소에 우선순위가 가장 높은 요소 (최소값, 최대값 등등)가 위치한다.
(오름차순) 최대값이 루트가 되게끔 배열로 구현하면 맨 앞 인덱스에 요소의 최대값이 위치한다.
이를 맨 마지막 요소와 교환한다.
최대값이 맨 마지막 인덱스에 위치했으므로 해당 요소는 더 이상 신경쓰지 않아도 된다.
그리고서, 맨 마지막 요소를 제외한 나머지 배열을 다시 힙 자료구조에 맞게 배치한다.
나머지 배열 중 맨 앞 인덱스와 맨 마지막 인덱스 요소끼리 교환한다.
위와 같은 과정을 반복하면 된다.
안정적이지 않다.
1 사이클 돌 때 완전이진트리의 깊이만큼만 비교하면 되기 때문에 O(logN)의 시간복잡도를 가진다.
따라서 최종 시간복잡도는 최악일 때도 O(NlogN)이다.
댓글