힙 정렬은 이진 힙 데이터 구조를 기반으로 하는 정렬 기술입니다. 힙 정렬을 진행하기 위해서는 바이너리 트리와 바이너리 힙에 대해 잘 알고 있어야 합니다.
완전 이진 트리란 무엇입니까?
완전한 이진 트리는 마지막 레벨을 제외한 모든 레벨이 완전히 채워진 트리 데이터 구조입니다. 마지막 레벨은 왼쪽부터 채워야 합니다.
이진 힙이란 무엇입니까?
이진 힙은 이진 트리의 특수한 경우입니다. 바이너리 힙에는 두 가지 유형이 있습니다 -
-
Max Heap - 각 레벨의 상위 노드는 하위 노드보다 큽니다.
-
Min Heap - 각 레벨의 상위 노드는 하위 노드보다 작습니다.
완전한 이진 트리의 배열 표현
바이너리 힙은 공간 효율적이기 때문에 배열로 표현할 수 있습니다. 부모 노드가 인덱스 I에 저장되어 있으면 왼쪽 자식은 2 * i + 1, 오른쪽 자식은 2 *i + 2로 계산할 수 있습니다. 인덱스가 0부터 시작한다고 가정합니다.
힙 정렬 알고리즘
-
완전한 바이너리 트리에서 최대 힙을 빌드합니다.
-
루트를 제거하고 힙의 마지막 요소로 교체하고 힙의 크기를 1 줄이고 나머지 노드에서 다시 최대 힙을 만듭니다.
-
노드가 1개만 남을 때까지 2단계를 반복합니다.
완전한 바이너리 트리에서 최대 힙 빌드
이것은 두 개의 자식 노드가 루트와 비교되는 완전한 이진 트리에서 최대 힙을 빌드하기 위한 코드입니다. Larger 요소가 루트가 아니면 더 큰 요소를 루트로 바꿉니다. 이것은 재귀적 절차입니다. 자식 노드보다 작은 현재 루트는 올바른 위치에 도달하지 않는 한 하위 하위 트리와 지속적으로 비교됩니다.
다음 코드는 기본적으로 정렬하려는 배열인 완전한 이진 트리에서 최대 힙을 빌드합니다.
def heapify(arr, n, i): # Find largest among root and children largest = i l = 2 * i + 1 r = 2 * i + 2 if l < n and arr[i] < arr[l]: largest = l if r < n and arr[largest] < arr[r]: largest = r # If root is not largest, swap with largest and continue heapifying if largest != i: arr[i], arr[largest] = arr[largest], arr[i] heapify(arr, n, largest)
힙 정렬
현재 최대 힙이 있습니다. 이제 다음 작업을 수행해야 합니다.
-
루트를 힙의 마지막 요소로 바꿉니다.
-
힙의 크기를 1만큼 줄입니다.(즉, 가장 큰 요소가 마지막 위치에 도달했음을 의미하므로 해당 요소를 고려할 필요가 없습니다).
-
마지막 요소를 제외하고 최대 힙을 다시 작성합니다.
-
요소가 1개만 남을 때까지 위의 단계를 반복합니다.
for i in range(n-1, 0, -1): # Swap arr[i], arr[0] = arr[0], arr[i] # Heapify root element heapify(arr, i, 0)
파이썬에서 힙 정렬을 위한 완전한 프로그램은 다음과 같습니다 -
def heapify(arr, n, i):
# Find largest among root and children
largest = i
l = 2 * i + 1
r = 2 * i + 2
if l < n and arr[i] < arr[l]:
largest = l
if r < n and arr[largest] < arr[r]:
largest = r
# If root is not largest, swap with largest and continue heapifying
if largest != i:
arr[i], arr[largest] = arr[largest], arr[i]
heapify(arr, n, largest)
def heapSort(arr):
n = len(arr)
# Build max heap
for i in range(n//2, -1, -1):
heapify(arr, n, i)
for i in range(n-1, 0, -1):
# Swap
arr[i], arr[0] = arr[0], arr[i]
# Heapify root element
heapify(arr, i, 0)
arr = [1, 12, 9, 5, 6, 10]
heapSort(arr)
n = len(arr)
print("Sorted array is")
for i in range(n):
print(arr[i], end=' ') 시간 복잡도 - O(n logn)