Maison >développement back-end >Tutoriel Python >Concept et code d'implémentation d'un algorithme de tri par tas en Python
La condition préalable pour comprendre l'algorithme de tri par tas est de connaître l'arbre binaire complet et la structure des données du tas. L'algorithme de tri par tas visualise le tableau comme un arbre binaire complet, c'est pourquoi il est également appelé « tas ».
1 Selon l'attribut de tas maximum, le plus grand élément du groupe de données est stocké dans le nœud racine
2. Supprimez l'élément racine et placez-le à la fin du tableau (le nième position), et placez le dernier élément de l'élément de l'arborescence, placez-le dans l'espace vide.
3. Réduisez la taille du tas de 1.
4. Regroupez à nouveau l'élément racine
5. Répétez le processus jusqu'à ce que tous les éléments de la liste soient triés
指定数组arr= 1 12 9 5 6 10 def heapify(arr, n, i): largest = i l = 2 * i + 1 r = 2 * i + 2 if l < n and arr[i] < arr[l]: largest = l if r < n and arr[largest] < arr[r]: largest = r heapifying if largest != i: arr[i], arr[largest] = arr[largest], arr[i] heapify(arr, n, largest) def heapSort(arr): n = len(arr) for i in range(n//2, -1, -1): heapify(arr, n, i) for i in range(n-1, 0, -1): arr[i], arr[0] = arr[0], arr[i] heapify(arr, i, 0) arr = [1, 12, 9, 5, 6, 10] heapSort(arr) n = len(arr) print("Sorted array is") for i in range(n): print("%d " % arr[i], end='').
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!