heap
,
Heap Sort는 heap 자료구조를 기반으로 정렬을 수행하는 알고리즘입니다. 내림차순 정렬을 위해서는 최대 힙, 오름차순을 위해서는 최소 힙 자료구조를 사용할 수 있습니다. 주어진 배열의 n개의 요소를 Heap에 삽입하고, 하나씩 삭제하면서 이를 새로운 배열에 저장하는 방식으로 정렬을 수행할 수 있습니다. Heap 자료구조에서 삽입/삭제는 O(logN)의 시간복잡도로 수행되므로, n개의 요소들을 모두 삽입/삭제하는데에는 O(NlogN)의 시간복잡도로 수행됩니다.
Heap Tree의 전체 높이 = logN
=> 삽입/삭제 => logN
요소의 개수 = n
T(n) = NlogN
# 힙 정렬
def heapify(unsorted, index, heap_size):
largest = index
left = 2 * index + 1
right = 2 * index + 2
if left < heap_size and unsorted[right] > unsorted[largest]:
largest = left
if right < heap_size and unsorted[right] > unsorted[largest]:
largest = right
if largest != index:
unsorted[largest], unsorted[index] = unsorted[index], unsorted[largest]
heapify(unsorted, largest, heap_size)
def heap_sort(unsorted):
n = len(unsorted)
for i in range(n // 2 - 1, -1, -1):
heapify(unsorted, i, n)
for i in range(n - 1, 0, -1):
unsorted[0], unsorted[i] = unsorted[i], unsorted[0]
heapify(unsorted, 0, i)
return unsorted