Python에서 힙 정렬을 구현하는 방법(코드 예)

이 기사의 내용은 Python에서 힙 정렬을 구현하는 방법(코드 예제)입니다. 특정 참고 값이 있으므로 도움이 될 수 있기를 바랍니다.

Heap sort

Heapsort는 힙의 데이터 구조를 이용하여 설계된 정렬 알고리즘을 말합니다. 스태킹은 완전한 이진 트리에 근접하는 구조이면서 동시에 스태킹의 속성을 만족합니다. 즉, 자식 노드의 키 값이나 인덱스는 항상 부모 노드보다 작거나 큽니다(그러나 모든 왼쪽 하위 트리가 오른쪽 하위 트리보다 작다는 보장은 없으며 그 반대도 마찬가지입니다. 힙 정렬(Heap Sort)은 힙(Heap)의 개념을 이용한 선택 정렬(Selection Sort)이라고 할 수 있습니다. 두 가지 방법으로 나뉩니다:

큰 상위 힙: 각 노드의 값은 힙 정렬 알고리즘에서 오름차순으로 사용되는 하위 노드의 값보다 크거나 같습니다.

# 🎜🎜 #작은 상위 힙: 각 노드의 값은 힙 정렬 알고리즘에서 내림차순으로 사용되는 하위 노드의 값보다 작거나 같습니다.

힙 정렬의 평균 시간 복잡도 는 Ο(nlogn) 입니다.

알고리즘 단계

1. 힙 생성 H[0...n-1](** non -리프 노드 노드는 힙을 구축하도록 조정됩니다**)

2. 힙의 헤드(최대값)와 힙의 테일을 바꿉니다.

3. 힙 크기를 1만큼 줄이고, Shift_down(0)을 호출하여 새 배열의 상위 데이터를 해당 위치

4로 조정합니다. 힙 크기가 1이 될 때까지 2단계를 반복합니다.

파이썬 코드 구현

def buildMaxHeap(arr):
    import math
    for i in range(math.floor(len(arr)/2),-1,-1):#构建堆由下往上构建所以用-1
        heapify(arr,i)

def heapify(arr, i):
    left = 2*i+1
    right = 2*i+2
    largest = i
    if left < arrLen and arr[left] > arr[largest]:
        largest = left
    if right < arrLen and arr[right] > arr[largest]:
        largest = right

    if largest != i:
        swap(arr, i, largest)
        heapify(arr, largest)

def swap(arr, i, j):
    arr[i], arr[j] = arr[j], arr[i]

def heapSort(arr):
    global arrLen
    arrLen = len(arr)
    buildMaxHeap(arr)
    for i in range(len(arr)-1,0,-1):
        swap(arr,0,i)
        arrLen -=1 #每次踢掉求出的最大值
        heapify(arr, 0)
    return arr

위 내용은 Python에서 힙 정렬을 구현하는 방법(코드 예)의 상세 내용입니다. 자세한 내용은 PHP 중국어 웹사이트의 기타 관련 기사를 참조하세요!