힙 자료구조에 이어 힙정렬에 대해 포스팅 해보겠습니다. 이전 포스팅에서 작성한 코드를 기준으로 작성하겠습니다.
힙정렬의 시간복잡도는 으로 빠른 정렬에 속합니다. 퀵정렬은 최악의 경우 의 성능을 내지만, 힙정렬은 안정적인 성능을 발휘한다고 합니다. 또한 추가적인 배열을 사용하지 않아 메모리 측면에서도 이점을 보입니다.
힙정렬은 삽입보다는 삭제과정만 이루어진다고 생각하시면 편합니다. 최대힙을 구현한 뒤, 루트노드 삭제하여 배열의 맨 마지막에 넣어주고, 깨진 힙을 재구조화하는 과정을 반복하면 힙정렬을 구현할 수 있습니다.
이전 힙 포스팅 중 down heapify 재귀함수 코드로 구현하면 다음과 같습니다.
def down_heap(array, index, heap_size):
parent = index
left_child = 2 * parent + 1
right_child = 2 * parent + 2
if left_child < heap_size and array[left_child] > array[parent]:
parent = left_child
if right_child < heap_size and array[right_child] > array[parent]:
parent = right_child
if parent != index:
array[parent], array[index] = array[index], array[parent]
make_heap(array, parent, heap_size)
# 부모노드가 되는 노드들만을 골라서 뒤에서부터 heapify를 차례로 실행
for root in range((N - 1) // 2, -1, -1):
make_heap(array, i, heap_size)
# 힙 정렬 수행
for i in range(N - 1, 0, -1):
array[0], array[i] = array[i], array[0]
down_heap(array, 0, i - 1)
이렇게 깔끔하게 정리된 글은 처음이에요! 정말 많이 배워갑니다. 앞으로도 포스팅 많이 해주세요!