/ PROGRAMING, PYTHON

힙정렬

힙정렬 Heap Sorting

힙정렬(Heap Sort)은 완전 이진트리 구조를 이용한 정렬 알고리즘으로서, 선택정렬(Selection Sort)의 개선된 버전으로 볼 수 있습니다. 힙정렬은 정렬되지 않은 리스트를 최대 힙(Max Heap)이나 최소 힙(Min Heap)으로 만든 다음, 루트 노드를 추출하여 정렬된 리스트에 추가하는 방식으로 동작합니다.

일반적인 단계

  1. 주어진 리스트를 최대 힙 또는 최소 힙으로 만듭니다.
    이를 위해서는 주어진 리스트를 이진 트리로 변환하고, 트리의 루트부터 시작하여 각 노드가 자식 노드보다 크거나 작은지 확인하면서 재배치합니다.
    이러한 과정을 “힙 만들기(heapify)”라고 합니다.

  2. 최대 힙 또는 최소 힙에서 루트 노드를 추출하고, 정렬된 리스트에 추가합니다.
    추출한 노드를 리스트의 맨 뒤에 배치합니다.

  3. 남은 노드들에 대해 1과 2의 과정을 반복합니다.

  4. 리스트가 완전히 정렬될 때까지 1~3의 과정을 반복합니다.

시간 복잡도

이 알고리즘의 시간 복잡도는 O(nlogn)으로, 안정적인 정렬 알고리즘 중에서는 빠른 편에 속합니다.
최악의 경우에도 O(nlogn)을 보장하기 때문에 대부분의 경우에 효율적인 정렬 알고리즘으로 사용됩니다.

힙정렬 1 (최대 힙으로 만들기)

def heap_sort(arr):
    n = len(arr)
    
    # 최대 힙으로 만들기
    for i in range(n // 2 - 1, -1, -1):
        heapify(arr, n , i)
        
    # 추출과 정렬
    for i in range(n - 1, 0 , -1):
        arr[0], arr[i] = arr[i], arr[0]
        heapify(arr, i, 0)
        
    return arr
        

def heap_sort(arr):
    n = len(arr)
    
    # 최대 힙으로 만들기
    for i in range(n // 2 - 1, -1, -1):
        heapify(arr, n , i)
    print("최대 힙으로 만들기")    
    print(arr)
    # 추출과 정렬
    for i in range(n - 1, 0, -1):
        arr[0], arr[i] = arr[i], arr[0]
        heapify(arr, i, 0)
        
    return arr

def heapify(arr, n, i):
    largest = i # 루트 노드
    left = 2 * i + 1  # 왼쪽 자식 노드
    right = 2 * i + 2  # 오른쪽 자식 노드
    
    # 왼쪽 자식과 비교
    if left < n and arr[left] > arr[largest]:
        largest = left
        
    # 오른쪽 자식과 비교
    if right < n and arr[right] > arr[largest]:
        largest = right
        
    # 루트 노드 변경
    if largest != i:
        arr[i], arr[largest] = arr[largest], arr[i]
        heapify(arr,n,largest)

arr = [ 3, 4 , 1, 2, 5]
arr_sort = heap_sort(arr)

최대 힙으로 만들기
[5, 4, 1, 2, 3]

print("추출 및 정렬")
print(arr_sort)

추출 및 정렬
[1, 2, 3, 4, 5]