이 기사에서 우리는 아래 주어진 문제 설명에 대한 해결책에 대해 배울 것입니다.
문제 설명 − 배열이 주어졌으므로 힙 정렬 개념을 사용하여 정렬해야 합니다.
여기서 우리는 끝에 최대 요소를 배치합니다. 이것은 배열이 정렬될 때까지 반복됩니다.
이제 아래 구현에서 솔루션을 살펴보겠습니다-
예
# heapify
def heapify(arr, n, i):
largest = i # largest value
l = 2 * i + 1 # left
r = 2 * i + 2 # right
# if left child exists
if l < n and arr[i] < arr[l]:
largest = l
# if right child exits
if r < n and arr[largest] < arr[r]:
largest = r
# root
if largest != i:
arr[i],arr[largest] = arr[largest],arr[i] # swap
# root.
heapify(arr, n, largest)
# sort
def heapSort(arr):
n = len(arr)
# maxheap
for i in range(n, -1, -1):
heapify(arr, n, i)
# element extraction
for i in range(n-1, 0, -1):
arr[i], arr[0] = arr[0], arr[i] # swap
heapify(arr, i, 0)
# main
arr = [2,5,3,8,6,5,4,7]
heapSort(arr)
n = len(arr)
print ("Sorted array is")
for i in range(n):
print (arr[i],end=" ") 출력
Sorted array is 2 3 4 5 5 6 7 8
모든 변수는 로컬 범위에서 선언되며 해당 참조는 위 그림과 같습니다.
결론
이 기사에서는 힙 정렬을 위한 Python 프로그램을 만드는 방법에 대해 배웠습니다.