Comment implémenter le tri par tas en python (exemple de code)

Le contenu de cet article explique comment implémenter le tri par tas en python (exemple de code). Il a une certaine valeur de référence. Les amis dans le besoin peuvent s'y référer.

Tri par tas

Le tri par tas fait référence à un algorithme de tri conçu en utilisant la structure de données d'un tas. L'empilement est une structure qui se rapproche d'un arbre binaire complet et satisfait en même temps aux propriétés de l'empilement : c'est-à-dire que la valeur clé ou l'index d'un nœud enfant est toujours plus petit (ou plus grand que) son nœud parent (mais il y a aucune garantie que tous les sous-arbres de gauche sont plus petits que le sous-arbre de droite, et vice versa également). Le tri par tas peut être considéré comme un tri par sélection qui utilise le concept de tas pour trier. Divisé en deux méthodes :

Big top tas : la valeur de chaque nœud est supérieure ou égale à la valeur de son nœud enfant, utilisée par ordre croissant dans l'algorithme de tri du tas

Small ; top tas : La valeur de chaque nœud est inférieure ou égale à la valeur de son nœud enfant, utilisée par ordre décroissant dans l'algorithme de tri par tas

La complexité temporelle moyenne du tri par tas est Ο(nlogn).

Étapes de l'algorithme

1. Créez un tas H[0...n-1] (**Ajustez les nœuds enfants des nœuds non-feuilles pour construire un tas **)

2. Échangez la tête du tas (valeur maximale) et la queue du tas

3. 0). Le but est de convertir le nouveau Ajustez les données en haut du tableau à la position correspondante

4. Répétez l'étape 2 jusqu'à ce que la taille du tas soit de 1.

Implémentation du code Python

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

Ce qui précède est le contenu détaillé de. pour plus d'informations, suivez d'autres articles connexes sur le site Web de PHP en chinois!