Heap Sort

• 개념 : 최대 힙 트리나 최소 힙 트리를 구성해 정렬 하는 방법, 내림차순-최대힙/오름차순-최소힙
• 특징
  • 힙(heap) : 완전 이진 트리, 우선순위 큐를 위해 만들어진 자료구조
• 장점
  • 시간복잡도 좋음. - $O(nlog_2n)$ 보장
  • 전체 레코드 정렬 없이 가장 큰 레코드 몇개만 필요할 때 가장 유용함.
• 단점
  • 조금 느린 편
  • unstable
  • swap이 많아서 시간연산 커짐
  • heapify
• 시간복잡도 : $O(nlog_2n)$ (모두 동일)
• 공간복잡도 : $O(1)$

arr = [4,2,5,6,1,3]

# Solution 1
a = [3,1,2,5,4,6]

def heap_sort(a):
    for i in range(1, len(a)):
        c = i
        while c!=0:
            r = (c-1) // 2
            if a[r] < a[c]:
                a[r], a[c] = a[c], a[r]
            c = r
    for j in range(len(a)-1, -1, -1):
        a[0], a[j] = a[j], a[0]
        r = 0
        c = 1
        
        while c<j:
            c = 2 * r + 1
            if c < j-1 and a[c] < a[c+1]:
                c += 1
            if c< j and a[r] < a[c]:
                a[r], a[c] = a[c], a[r]
            
            r=c
heap_sort(a)
print(a)

# Solution 2
a = [3,1,2,5,4,6]

def heapify(arr, index, heap_size):
    largest = index 
    left_index = 2 * index + 1 
    right_index = 2 * index + 2 
    if left_index < heap_size and arr[left_index] > arr[largest]: 
        largest = left_index 
    if right_index < heap_size and arr[right_index] > arr[largest]:
        largest = right_index 
    if largest != index:
        arr[largest], arr[index] = arr[index], arr[largest] 
        heapify(arr, largest, heap_size) 
                
def heap_sort(arr): 
    length = len(arr) 
    for i in range(length // 2 - 1, -1, -1):
        heapify(arr, i, length) 
    for i in range(length - 1, 0 , -1):
        arr[0], arr[i] = arr[i], arr[0]
        heapify(arr, 0, i) 
    return arr

heap_sort(a)
print(a)