Dans ce didacticiel, vous apprendrez comment fonctionne l'algorithme de tri de tas. Vous trouverez également des exemples fonctionnels de tri de tas en C, C ++, Java et Python.
Heap Sort est un algorithme de tri populaire et efficace en programmation informatique. Apprendre à écrire l'algorithme de tri de tas nécessite la connaissance de deux types de structures de données: les tableaux et les arbres.
L'ensemble initial de nombres que nous voulons trier est stocké dans un tableau par exemple (10, 3, 76, 34, 23, 32)et après le tri, nous obtenons un tableau trié(3,10,23,32,34,76)
Le tri de tas fonctionne en visualisant les éléments du tableau sous la forme d'un type spécial d'arbre binaire complet appelé tas.
Au préalable, vous devez connaître une arborescence binaire complète et une structure de données de tas.
Relation entre les index de tableau et les éléments de l'arborescence
Un arbre binaire complet a une propriété intéressante que nous pouvons utiliser pour trouver les enfants et les parents de n'importe quel nœud.
Si l'index d'un élément du tableau est i, l'élément de l'index 2i+1deviendra l'enfant de gauche et l'élément de l' 2i+2index deviendra l'enfant de droite. De plus, le parent de tout élément à l'index i est donné par la borne inférieure de (i-1)/2.
Relation entre les indices de tableau et de tas
Testons-le,
Enfant gauche de 1 (index 0) = élément dans (2 * 0 + 1) index = élément dans 1 index = 12 Enfant droit de 1 = élément dans (2 * 0 + 2) index = élément dans 2 index = 9 De même, Enfant gauche de 12 (index 1) = élément dans (2 * 1 + 1) index = élément dans 3 index = 5 Enfant droit de 12 = élément dans (2 * 1 + 2) index = élément dans 4 index = 6
Confirmons également que les règles sont valables pour trouver le parent de n'importe quel nœud
Parent de 9 (position 2) = (2-1) / 2 = ½ = 0,5 ~ 0 index = 1 Parent de 12 (position 1) = (1-1) / 2 = 0 index = 1
Comprendre ce mappage des index de tableau aux positions de l'arborescence est essentiel pour comprendre le fonctionnement de la structure de données du tas et comment elle est utilisée pour implémenter le tri du tas.
Qu'est-ce que la structure de données du tas?
Heap est une structure de données spéciale basée sur une arborescence. On dit qu'un arbre binaire suit une structure de données de tas si
- c'est un arbre binaire complet
- Tous les nœuds de l'arborescence suivent la propriété qu'ils sont plus grands que leurs enfants, c'est-à-dire que le plus grand élément est à la racine et ses deux enfants et plus petit que la racine et ainsi de suite. Un tel tas est appelé un tas max. Si au contraire, tous les nœuds sont plus petits que leurs enfants, cela s'appelle un tas min
L'exemple de diagramme suivant montre Max-Heap et Min-Heap.
Heap max et tas min
Pour en savoir plus, consultez la page Structure des données du tas.
Comment "heapifier" un arbre
À partir d'un arbre binaire complet, nous pouvons le modifier pour devenir un Max-Heap en exécutant une fonction appelée heapify sur tous les éléments non-feuilles du tas.
Étant donné que heapify utilise la récursivité, cela peut être difficile à comprendre. Alors, réfléchissons d'abord à la façon dont vous pourriez entasser un arbre avec seulement trois éléments.
heapify(array) Root = array(0) Largest = largest( array(0) , array (2*0 + 1). array(2*0+2)) if(Root != Largest) Swap(Root, Largest) 
Cas de base Heapify
L'exemple ci-dessus montre deux scénarios - l'un dans lequel la racine est l'élément le plus grand et nous n'avons rien à faire. Et un autre dans lequel la racine avait un élément plus grand en tant qu'enfant et nous devions permuter pour maintenir la propriété max-heap.
Si vous avez déjà travaillé avec des algorithmes récursifs, vous avez probablement identifié que cela doit être le cas de base.
Pensons maintenant à un autre scénario dans lequel il y a plus d'un niveau.
Comment heapify élément racine lorsque ses sous-arbres sont déjà des tas max
L'élément supérieur n'est pas un tas max mais tous les sous-arbres sont des tas max.
Pour conserver la propriété max-heap pour l'ensemble de l'arbre, nous devrons continuer à pousser 2 vers le bas jusqu'à ce qu'il atteigne sa position correcte.
Comment heapify élément racine lorsque ses sous-arbres sont des tas max
Ainsi, pour conserver la propriété max-heap dans une arborescence où les deux sous-arbres sont des max-heaps, nous devons exécuter heapify sur l'élément racine à plusieurs reprises jusqu'à ce qu'il soit plus grand que ses enfants ou qu'il devienne un nœud feuille.
Nous pouvons combiner ces deux conditions dans une fonction heapify comme
void heapify(int arr(), int n, int i) ( // Find largest among root, left child and right child int largest = i; int left = 2 * i + 1; int right = 2 * i + 2; if (left arr(largest)) largest = left; if (right arr(largest)) largest = right; // Swap and continue heapifying if root is not largest if (largest != i) ( swap(&arr(i), &arr(largest)); heapify(arr, n, largest); ) )
Cette fonction fonctionne à la fois pour le cas de base et pour un arbre de toute taille. Nous pouvons ainsi déplacer l'élément racine à la bonne position pour maintenir l'état de tas max pour n'importe quelle taille d'arbre tant que les sous-arbres sont des tas max.
Construire max-heap
Pour construire un tas max à partir de n'importe quel arbre, nous pouvons donc commencer à entasser chaque sous-arbre de bas en haut et finir avec un tas max après que la fonction est appliquée à tous les éléments, y compris l'élément racine.
Dans le cas d'un arbre complet, le premier index d'un nœud non feuille est donné par n/2 - 1. Tous les autres nœuds après cela sont des nœuds feuilles et n'ont donc pas besoin d'être entassés.
Ainsi, nous pouvons créer un tas maximum comme
// Build heap (rearrange array) for (int i = n / 2 - 1; i>= 0; i--) heapify(arr, n, i); 
Créer un tableau et calculer i 
Étapes pour créer le tas maximal pour le tri du tas 
Étapes pour créer le tas maximal pour le tri du tas 
Étapes pour créer le tas maximal pour le tri du tas
Comme le montre le diagramme ci-dessus, nous commençons par entasser les plus petits arbres les plus bas et remontons progressivement jusqu'à ce que nous atteignions l'élément racine.
Si vous avez tout compris jusqu'ici, félicitations, vous êtes sur la bonne voie pour maîtriser le tri Heap.
Comment fonctionne le tri en tas?
- Puisque l'arborescence satisfait la propriété Max-Heap, le plus gros élément est stocké au nœud racine.
- Swap: Supprimez l'élément racine et placez-le à la fin du tableau (nième position) Placez le dernier élément de l'arborescence (tas) à l'endroit vacant.
- Supprimer: réduisez la taille du tas de 1.
- Heapify: Heapify l'élément racine à nouveau afin que nous ayons l'élément le plus élevé à la racine.
- Le processus est répété jusqu'à ce que tous les éléments de la liste soient triés.
Swap, Remove et Heapify
Le code ci-dessous montre l'opération.
// Heap sort for (int i = n - 1; i>= 0; i--) ( swap(&arr(0), &arr(i)); // Heapify root element to get highest element at root again heapify(arr, i, 0); )
Exemples Python, Java et C / C ++
Python Java C C ++ # Heap Sort in python def heapify(arr, n, i): # Find largest among root and children 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 # If root is not largest, swap with largest and continue heapifying if largest != i: arr(i), arr(largest) = arr(largest), arr(i) heapify(arr, n, largest) def heapSort(arr): n = len(arr) # Build max heap for i in range(n//2, -1, -1): heapify(arr, n, i) for i in range(n-1, 0, -1): # Swap arr(i), arr(0) = arr(0), arr(i) # Heapify root element 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='')
// Heap Sort in Java public class HeapSort ( public void sort(int arr()) ( int n = arr.length; // Build max heap for (int i = n / 2 - 1; i>= 0; i--) ( heapify(arr, n, i); ) // Heap sort for (int i = n - 1; i>= 0; i--) ( int temp = arr(0); arr(0) = arr(i); arr(i) = temp; // Heapify root element heapify(arr, i, 0); ) ) void heapify(int arr(), int n, int i) ( // Find largest among root, left child and right child int largest = i; int l = 2 * i + 1; int r = 2 * i + 2; if (l arr(largest)) largest = l; if (r arr(largest)) largest = r; // Swap and continue heapifying if root is not largest if (largest != i) ( int swap = arr(i); arr(i) = arr(largest); arr(largest) = swap; heapify(arr, n, largest); ) ) // Function to print an array static void printArray(int arr()) ( int n = arr.length; for (int i = 0; i < n; ++i) System.out.print(arr(i) + " "); System.out.println(); ) // Driver code public static void main(String args()) ( int arr() = ( 1, 12, 9, 5, 6, 10 ); HeapSort hs = new HeapSort(); hs.sort(arr); System.out.println("Sorted array is"); printArray(arr); ) )
// Heap Sort in C #include // Function to swap the the position of two elements void swap(int *a, int *b) ( int temp = *a; *a = *b; *b = temp; ) void heapify(int arr(), int n, int i) ( // Find largest among root, left child and right child int largest = i; int left = 2 * i + 1; int right = 2 * i + 2; if (left arr(largest)) largest = left; if (right arr(largest)) largest = right; // Swap and continue heapifying if root is not largest if (largest != i) ( swap(&arr(i), &arr(largest)); heapify(arr, n, largest); ) ) // Main function to do heap sort void heapSort(int arr(), int n) ( // Build max heap for (int i = n / 2 - 1; i>= 0; i--) heapify(arr, n, i); // Heap sort for (int i = n - 1; i>= 0; i--) ( swap(&arr(0), &arr(i)); // Heapify root element to get highest element at root again heapify(arr, i, 0); ) ) // Print an array void printArray(int arr(), int n) ( for (int i = 0; i < n; ++i) printf("%d ", arr(i)); printf(""); ) // Driver code int main() ( int arr() = (1, 12, 9, 5, 6, 10); int n = sizeof(arr) / sizeof(arr(0)); heapSort(arr, n); printf("Sorted array is "); printArray(arr, n); )
// Heap Sort in C++ #include using namespace std; void heapify(int arr(), int n, int i) ( // Find largest among root, left child and right child int largest = i; int left = 2 * i + 1; int right = 2 * i + 2; if (left arr(largest)) largest = left; if (right arr(largest)) largest = right; // Swap and continue heapifying if root is not largest if (largest != i) ( swap(arr(i), arr(largest)); heapify(arr, n, largest); ) ) // main function to do heap sort void heapSort(int arr(), int n) ( // Build max heap for (int i = n / 2 - 1; i>= 0; i--) heapify(arr, n, i); // Heap sort for (int i = n - 1; i>= 0; i--) ( swap(arr(0), arr(i)); // Heapify root element to get highest element at root again heapify(arr, i, 0); ) ) // Print an array void printArray(int arr(), int n) ( for (int i = 0; i < n; ++i) cout << arr(i) << " "; cout << ""; ) // Driver code int main() ( int arr() = (1, 12, 9, 5, 6, 10); int n = sizeof(arr) / sizeof(arr(0)); heapSort(arr, n); cout << "Sorted array is "; printArray(arr, n); )
Complexité du tri en tas
Le tri en tas a des O(nlog n)complexités temporelles pour tous les cas (meilleur cas, cas moyen et pire cas).
Laissez-nous comprendre pourquoi. La hauteur d'un arbre binaire complet contenant n éléments estlog n
As we have seen earlier, to fully heapify an element whose subtrees are already max-heaps, we need to keep comparing the element with its left and right children and pushing it downwards until it reaches a point where both its children are smaller than it.
In the worst case scenario, we will need to move an element from the root to the leaf node making a multiple of log(n) comparisons and swaps.
During the build_max_heap stage, we do that for n/2 elements so the worst case complexity of the build_heap step is n/2*log n ~ nlog n.
During the sorting step, we exchange the root element with the last element and heapify the root element. For each element, this again takes log n worst time because we might have to bring the element all the way from the root to the leaf. Since we repeat this n times, the heap_sort step is also nlog n.
Also since the build_max_heap and heap_sort steps are executed one after another, the algorithmic complexity is not multiplied and it remains in the order of nlog n.
Also it performs sorting in O(1) space complexity. Compared with Quick Sort, it has a better worst case ( O(nlog n) ). Quick Sort has complexity O(n^2) for worst case. But in other cases, Quick Sort is fast. Introsort is an alternative to heapsort that combines quicksort and heapsort to retain advantages of both: worst case speed of heapsort and average speed of quicksort.
Heap Sort Applications
Systems concerned with security and embedded systems such as Linux Kernel use Heap Sort because of the O(n log n) upper bound on Heapsort's running time and constant O(1) upper bound on its auxiliary storage.
Bien que le tri en tas ait une O(n log n)complexité temporelle, même dans le pire des cas, il n'a pas plus d'applications (par rapport à d'autres algorithmes de tri comme le tri rapide, le tri par fusion). Cependant, sa structure de données sous-jacente, le tas, peut être utilisée efficacement si nous voulons extraire le plus petit (ou le plus grand) de la liste des éléments sans avoir à conserver les éléments restants dans l'ordre trié. Pour par exemple les files d'attente prioritaires.
