[427] 힙 정렬(Heap Sort)

1. 힙 정렬 개념

힙 정렬은 영국의 컴퓨터 과학자 J. W. J. Williams가 1964년 고안한 정렬 알고리즘입니다.

힙이라는 자료구조를 만들어 원소를 차례대로 정렬해 나가는 과정을 거칩니다.

 

힙은 완전이진트리를 이용하여 최대값이나 최소값을 쉽게 찾아내는 자료구조입니다.

최대값을 쉽게 찾는 힙을 최대 힙, 최소값을 쉽게 찾는 힙을 최소 힙이라고 부릅니다.

이런 특성 때문에 일반적으로 힙을 사용하여 (크기를 우선순위로 가지는) 우선순위 큐를 구현합니다.

 

힙 정렬은 두 단계를 거칩니다.

먼저 모든 원소를 최대 힙으로 만듭니다.(힙 생성 단계, \(O(n)\))

그 다음 최대 값을 하나 꺼내고, 나머지 부분을 힙으로 재구성하는 과정을 반복합니다.(정렬 단계, \(O(n\log{n})\))

 

힙 정렬은 완전이진트리 형태의 힙을 이용하기 때문에 전체 시간 복잡도는 \(\boldsymbol{O(n\log{n})}\)이며 데이터의 초기 상태와 관계 없이 안정적인 성능을 제공합니다.

주어진 배열을 힙으로 만드는 과정에서 별도의 공간을 필요로 하지 않으므로 제자리 정렬(In-place Sorting)이 가능합니다.

 

https://ko.wikipedia.org/wiki/힙_정렬

힙 정렬 - 위키백과, 우리 모두의 백과사전

2. 힙 정렬 예제

처음 단계에서는 힙이 구성이 되어있지 않기 때문에 전체 배열을 힙으로 만듭니다.(힙 생성 단계)

이후 최대값을 하나씩 맨 뒤로 swap하고 힙 재구성을 실시합니다.(정렬 단계)(힙에서 원소를 삭제하는 과정과 같습니다.)

배열의 크기가 1이 될 때까지 반복하면 정렬이 완성됩니다.

3. 힙 정렬 코드

nums = [6, 1, 2, 5, 7, 3, 4]

# 힙 생성 단계
def heapify(nums):
    for i in range(len(nums)//2-1, -1, -1): # 최하위 부모 노드부터 root 노드 방향으로 힙 구성
        largest = i
        left = 2 * i + 1
        right = 2 * i + 2
        if left < len(nums) and nums[left] > nums[largest]:
            largest = left
        if right < len(nums) and nums[right] > nums[largest]:
            largest = right
        if largest != i:
            nums[i], nums[largest] = nums[largest], nums[i]

# 정렬 단계
def sort(nums, last):
    nums[0], nums[last] = nums[last], nums[0]

    largest = 0
    while True: # 최상위 노드 빼내고 내려가며 힙 재구성
        i = largest
        left = 2 * i + 1
        right = 2 * i + 2
        if left < last and nums[left] > nums[largest]:
            largest = left
        if right < last and nums[right] > nums[largest]:
            largest = right
        if largest != i:
            nums[i], nums[largest] = nums[largest], nums[i]
        else:
            break
        
def heap_sort(nums):
	# 힙 생성 단계
    heapify(nums)
    
    # 힙 정렬 단계
    for i in range(len(nums)-1, 0, -1):
        sort(nums, i)

heap_sort(nums)
print(nums)
# [1, 2, 3, 4, 5, 6, 7]

4. 힙 정렬 장점

힙 정렬의 시간 복잡도는 최선, 최악, 평균 모두 \(O(n\log{n})\)으로 데이터의 초기 상태에 관계없이 일관된 성능을 보장합니다.

주어진 배열 안에서 힙을 구성하여 정렬을 수행하므로 제자리 정렬(In-place Sorting)이 가능하여 메모리 효율성이 높습니다.

5. 힙 정렬 단점

힙 정렬은 안정적인 정렬이 아니므로 동일한 값을 가진 원소의 상대적인 위치가 정렬 후에 바뀔 수 있습니다.

힙을 생성하고 재구성하는 과정에서 비선형적으로 배열에 접근하기 때문에 퀵 정렬과 같은 알고리즘에 비해 캐시 성능이 떨어질 수 있습니다.

힙이라는 자료구조를 이해하고 구현하는데 추가적인 복잡성을 요구합니다.

6. 정렬 알고리즘 시간 복잡도 비교

정렬 알고리즘	최악(Worst)	최선(Best)	평균(Average)
버블 정렬(Bubble Sort)	\(O(n^2)\)	\(O(n^2)\)	\(O(n^2)\)
선택 정렬(Selection Sort)	\(O(n^2)\)	\(O(n^2)\)	\(O(n^2)\)
삽입 정렬(Insertion Sort)	\(O(n^2)\)	\(O(n)\)	\(O(n^2)\)
퀵 정렬(Quick Sort)	\(O(n^2)\)	\(O(n\log{n})\)	\(O(n\log{n})\)
병합 정렬(Merge Sort)	\(O(n\log{n})\)	\(O(n\log{n})\)	\(O(n\log{n})\)
힙 정렬(Heap Sort)	\(\boldsymbol{O(n\log{n})}\)	\(\boldsymbol{O(n\log{n})}\)	\(\boldsymbol{O(n\log{n})}\)
기수 정렬(Radix Sort)	\(O(n)\)	\(O(n)\)	\(O(n)\)
계수 정렬(Counting Sort)	\(O(n)\)	\(O(n)\)	\(O(n)\)