Comment implémenter un algorithme de tri par tas en utilisant Python ?

Comment implémenter un algorithme de tri par tas en utilisant Python ?

Le tri par tas est un algorithme de tri basé sur un tas binaire, qui tire parti des propriétés d'un arbre binaire complet. Les tas peuvent être divisés en deux types : tas max et tas min. Le tas max nécessite que la valeur du nœud parent soit supérieure ou égale à la valeur de ses nœuds enfants, tandis que le tas min nécessite que la valeur du nœud parent soit supérieure ou égale à la valeur de ses nœuds enfants. est inférieur ou égal à la valeur de ses nœuds enfants. Dans l'algorithme de tri par tas, nous utilisons le tas maximum.

Voici les étapes spécifiques et les exemples de code pour utiliser Python pour implémenter le tri des tas :

Étape 1 : Construire le tas maximum
Dans le processus de construction du tas maximum, nous devons ajuster la structure du tas afin que la valeur de chaque nœud parent est supérieur ou égal à sa valeur La valeur du nœud enfant.

Tout d'abord, nous définissons une fonction heapify pour implémenter le processus d'ajustement du tas. Cette fonction accepte trois paramètres : le tas de la liste des tas, la taille du tas et l'index du nœud parent à ajuster.

def heapify(heap, size, parent):
    largest = parent
    left = 2 * parent + 1
    right = 2 * parent + 2

    if left < size and heap[left] > heap[largest]:
        largest = left

    if right < size and heap[right] > heap[largest]:
        largest = right

    if largest != parent:
        heap[parent], heap[largest] = heap[largest], heap[parent]
        heapify(heap, size, largest)

Ensuite, nous définissons une fonction build_heap pour construire le tas maximum. Cette fonction accepte une liste comme argument et construit un tas maximum basé sur les éléments de la liste.

def build_heap(heap):
    size = len(heap)

    for i in range(size // 2 - 1, -1, -1):
        heapify(heap, size, i)

Étape 2 : Tri par tas
Après avoir construit le tas max, nous pouvons utiliser les propriétés du tas max pour le tri. L'idée du tri du tas est d'échanger l'élément supérieur du tas (valeur maximale) avec le dernier élément à chaque fois, d'ajuster le haut du tas, puis de retirer la valeur maximale, et d'ajuster à nouveau jusqu'à ce qu'il n'y ait que un élément restant dans le tas.

Voici les étapes spécifiques et des exemples de code pour le tri à l'aide de l'algorithme de tri par tas :

def heap_sort(heap):
    size = len(heap)

    build_heap(heap)

    for i in range(size - 1, 0, -1):
        heap[0], heap[i] = heap[i], heap[0]
        heapify(heap, i, 0)

Étape 3 : tester le code
Maintenant, nous pouvons utiliser certaines données de test pour vérifier que notre code est correct.

if __name__ == "__main__":
    # 测试数据
    data = [4, 10, 3, 5, 1]

    heap_sort(data)

    print("排序结果:", data)

Exécutez le code ci-dessus et le résultat de sortie est : Résultat du tri : [1, 3, 4, 5, 10], indiquant que l'algorithme de tri du tas est correct.

Résumé :
Le tri par tas est un algorithme de tri efficace avec une complexité temporelle de O(nlogn). En tirant parti des propriétés complètes de l'arbre binaire du tas, nous pouvons y parvenir en construisant un tas maximum et en effectuant un tri par tas. En utilisant le langage Python, nous pouvons implémenter l'algorithme de tri du tas en écrivant la fonction d'ajustement du tas (heapify), la fonction de création de tas maximale (build_heap) et la fonction de tri du tas (heap_sort). Le code de test nous aide à vérifier que notre implémentation est correcte.

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!