힙 정렬 알고리즘
힙 정렬의 정의
힙 정렬: 데이터 구조를 기반으로 하는 가장 효율적인 정렬 알고리즘 중 하나입니다.
힙소트의 공간 및 시간 복잡도
힙 정렬 알고리즘의 공간 복잡도는 O(1)입니다.
베스트 케이스
평균 케이스
최악의 경우
오(n 로그 n)
오(n 로그 n)
오(n 로그 n)
힙 정렬 방식
파이썬에서 힙 정렬 알고리즘 구현
힙파이 기능
def heapify(arr, n, i):
largest = i # Initialize largest as root
l = 2 * i + 1 # left = 2*i + 1
r = 2 * i + 2 # right = 2*i + 2
# See if left child of root exists and is
# greater than root
if l < n and arr[largest] < arr[l]:
largest = l
# See if right child of root exists and is
# greater than root
if r < n and arr[largest] < arr[r]:
largest = r
# Change root, if needed
if largest != i:
arr[i], arr[largest] = arr[largest], arr[i] # swap
# Heapify the root.
heapify(arr, n, largest)
힙 정렬 기능
def heapSort(arr):
n = len(arr)
# Build a maxheap.
for i in range(n//2 - 1, -1, -1):
heapify(arr, n, i)
# One by one extract elements
for i in range(n-1, 0, -1):
arr[i], arr[0] = arr[0], arr[i] # swap
heapify(arr, i, 0)
참조 및 유용한 리소스
Reference
이 문제에 관하여(힙 정렬 알고리즘), 우리는 이곳에서 더 많은 자료를 발견하고 링크를 클릭하여 보았다 https://dev.to/ayabouchiha/heap-sort-algorithm-247h텍스트를 자유롭게 공유하거나 복사할 수 있습니다.하지만 이 문서의 URL은 참조 URL로 남겨 두십시오.
우수한 개발자 콘텐츠 발견에 전념 (Collection and Share based on the CC Protocol.)