Tri de tas en Java

1. Introduction

Dans ce didacticiel, nous verrons comment fonctionne le tri en tas et nous l'implémenterons en Java.

Le tri du tas est basé sur la structure de données du tas. Afin de comprendre correctement Heap Sort, nous allons d'abord explorer Heaps et comment ils sont implémentés.

2. Structure des données du tas

Un tas est une structure de données basée sur une arborescence spécialisée . Par conséquent, il est composé de nœuds. Nous affectons les éléments aux nœuds: chaque nœud contient exactement un élément.

De plus, les nœuds peuvent avoir des enfants. Si un nœud n'a pas d'enfants, nous l'appelons feuille.

Ce que Heap rend spécial, ce sont deux choses:

  1. la valeur de chaque nœud doit être inférieure ou égale à toutes les valeurs stockées dans ses enfants
  2. c'est un arbre complet , ce qui signifie qu'il a la hauteur la moins élevée possible

En raison de la 1ère règle, le moindre élément sera toujours à la racine de l'arbre .

La manière dont nous appliquons ces règles dépend de la mise en œuvre.

Les tas sont généralement utilisés pour implémenter des files d'attente prioritaires car Heap est une implémentation très efficace d'extraction du plus petit (ou du plus grand) élément.

2.1. Variantes de tas

Heap a de nombreuses variantes, toutes diffèrent par certains détails d'implémentation.

Par exemple, ce que nous avons décrit ci-dessus est un Min-Heap, car un parent est toujours inférieur à tous ses enfants . Sinon, nous aurions pu définir Max-Heap, auquel cas un parent est toujours supérieur à ses enfants. Par conséquent, le plus grand élément sera dans le nœud racine.

Nous pouvons choisir parmi de nombreuses implémentations d'arbres. Le plus simple est un arbre binaire. Dans un arbre binaire, chaque nœud peut avoir au plus deux enfants. Nous les appelons enfant de gauche et enfant de droite .

Le moyen le plus simple d'appliquer la 2e règle est d'utiliser un arbre binaire complet. Un arbre binaire complet suit quelques règles simples:

  1. si un nœud n'a qu'un seul enfant, cela devrait être son enfant gauche
  2. seul le nœud le plus à droite au niveau le plus profond peut avoir exactement un enfant
  3. les feuilles ne peuvent être qu'au niveau le plus profond

Voyons ces règles avec quelques exemples:

 1 2 3 4 5 6 7 8 9 10 () () () () () () () () () () / \ / \ / \ / \ / \ / / / \ () () () () () () () () () () () () () () / \ / \ / \ / / \ () () () () () () () () () / ()

Les arbres 1, 2, 4, 5 et 7 suivent les règles.

Les arbres 3 et 6 violent la 1ère règle, 8 et 9 la 2ème règle, et 10 violent la 3ème règle.

Dans ce didacticiel, nous allons nous concentrer sur Min-Heap avec une implémentation d' arbre binaire .

2.2. Insertion d'éléments

Nous devrions implémenter toutes les opérations de manière à conserver les invariants du tas. De cette façon, nous pouvons construire le tas avec des insertions répétées , nous allons donc nous concentrer sur l'opération d'insertion unique.

Nous pouvons insérer un élément avec les étapes suivantes:

  1. créer une nouvelle feuille qui est l'emplacement disponible le plus à droite au niveau le plus profond et stocker l'élément dans ce nœud
  2. si l'élément est inférieur à son parent, nous les échangeons
  3. continuez avec l'étape 2, jusqu'à ce que l'élément soit inférieur à son parent ou qu'il devienne la nouvelle racine

Notez que l'étape 2 ne violera pas la règle Heap, car si nous remplaçons la valeur d'un nœud par une valeur inférieure, elle sera toujours inférieure à ses enfants.

Voyons un exemple! Nous voulons insérer 4 dans ce tas:

 2 / \ / \ 3 6 / \ 5 7

La première étape consiste à créer une nouvelle feuille qui stocke 4:

 2 / \ / \ 3 6 / \ / 5 7 4

Puisque 4 est inférieur à son parent, 6, nous les échangeons:

 2 / \ / \ 3 4 / \ / 5 7 6

Maintenant, nous vérifions si 4 est inférieur à son parent ou non. Puisque son parent est 2, on s'arrête. Le tas est toujours valide et nous avons inséré le numéro 4.

Insérons 1:

 2 / \ / \ 3 4 / \ / \ 5 7 6 1

Nous devons échanger 1 et 4:

 2 / \ / \ 3 1 / \ / \ 5 7 6 4

Maintenant, nous devrions permuter 1 et 2:

 1 / \ / \ 3 2 / \ / \ 5 7 6 4

Puisque 1 est la nouvelle racine, nous nous arrêtons.

3. Implémentation du tas en Java

Puisque nous utilisons un arbre binaire complet, nous pouvons l'implémenter avec un tableau : un élément du tableau sera un nœud dans l'arbre. Nous marquons chaque nœud avec les indices du tableau de gauche à droite, de haut en bas de la manière suivante:

 0 / \ / \ 1 2 / \ / 3 4 5

La seule chose dont nous avons besoin est de garder une trace du nombre d'éléments que nous stockons dans l'arborescence. De cette façon, l'index de l'élément suivant que nous voulons insérer sera la taille du tableau.

En utilisant cette indexation, nous pouvons calculer l'index des nœuds parents et enfants:

  • parent: (index - 1) / 2
  • left child: 2 * index + 1
  • right child: 2 * index + 2

Since we don't want to bother with array reallocating, we'll simplify the implementation even more and use an ArrayList.

A basic Binary Tree implementation looks like this:

class BinaryTree { List elements = new ArrayList(); void add(E e) { elements.add(e); } boolean isEmpty() { return elements.isEmpty(); } E elementAt(int index) { return elements.get(index); } int parentIndex(int index) { return (index - 1) / 2; } int leftChildIndex(int index) { return 2 * index + 1; } int rightChildIndex(int index) { return 2 * index + 2; } }

The code above only adds the new element to the end of the tree. Therefore, we need to traverse the new element up if necessary. We can do it with the following code:

class Heap
    
      { // ... void add(E e) { elements.add(e); int elementIndex = elements.size() - 1; while (!isRoot(elementIndex) && !isCorrectChild(elementIndex)) { int parentIndex = parentIndex(elementIndex); swap(elementIndex, parentIndex); elementIndex = parentIndex; } } boolean isRoot(int index) { return index == 0; } boolean isCorrectChild(int index) { return isCorrect(parentIndex(index), index); } boolean isCorrect(int parentIndex, int childIndex) { if (!isValidIndex(parentIndex) || !isValidIndex(childIndex)) { return true; } return elementAt(parentIndex).compareTo(elementAt(childIndex)) < 0; } boolean isValidIndex(int index) { return index < elements.size(); } void swap(int index1, int index2) { E element1 = elementAt(index1); E element2 = elementAt(index2); elements.set(index1, element2); elements.set(index2, element1); } // ... }
    

Note, that since we need to compare the elements, they need to implement java.util.Comparable.

4. Heap Sort

Since the root of the Heap always contains the smallest element, the idea behind Heap Sort is pretty simple: remove the root node until the Heap becomes empty.

The only thing we need is a remove operation, which keeps the Heap in a consistent state. We must ensure that we don't violate the structure of the Binary Tree or the Heap property.

To keep the structure, we can't delete any element, except the rightmost leaf. So the idea is to remove the element from the root node and store the rightmost leaf in the root node.

But this operation will most certainly violate the Heap property. So if the new root is greater than any of its child nodes, we swap it with its least child node. Since the least child node is less than all other child nodes, it doesn't violate the Heap property.

We keep swapping until the element becomes a leaf, or it's less than all of its children.

Let's delete the root from this tree:

 1 / \ / \ 3 2 / \ / \ 5 7 6 4

First, we place the last leaf in the root:

 4 / \ / \ 3 2 / \ / 5 7 6

Then, since it's greater than both of its children, we swap it with its least child, which is 2:

 2 / \ / \ 3 4 / \ / 5 7 6

4 is less than 6, so we stop.

5. Heap Sort Implementation in Java

With all we have, removing the root (popping) looks like this:

class Heap
    
      { // ... E pop() { if (isEmpty()) { throw new IllegalStateException("You cannot pop from an empty heap"); } E result = elementAt(0); int lasElementIndex = elements.size() - 1; swap(0, lasElementIndex); elements.remove(lasElementIndex); int elementIndex = 0; while (!isLeaf(elementIndex) && !isCorrectParent(elementIndex)) { int smallerChildIndex = smallerChildIndex(elementIndex); swap(elementIndex, smallerChildIndex); elementIndex = smallerChildIndex; } return result; } boolean isLeaf(int index) { return !isValidIndex(leftChildIndex(index)); } boolean isCorrectParent(int index) { return isCorrect(index, leftChildIndex(index)) && isCorrect(index, rightChildIndex(index)); } int smallerChildIndex(int index) { int leftChildIndex = leftChildIndex(index); int rightChildIndex = rightChildIndex(index); if (!isValidIndex(rightChildIndex)) { return leftChildIndex; } if (elementAt(leftChildIndex).compareTo(elementAt(rightChildIndex)) < 0) { return leftChildIndex; } return rightChildIndex; } // ... }
    

Like we said before, sorting is just creating a Heap, and removing the root repeatedly:

class Heap
    
      { // ... static 
     
       List sort(Iterable elements) { Heap heap = of(elements); List result = new ArrayList(); while (!heap.isEmpty()) { result.add(heap.pop()); } return result; } static 
      
        Heap of(Iterable elements) { Heap result = new Heap(); for (E element : elements) { result.add(element); } return result; } // ... }
      
     
    

We can verify it's working with the following test:

@Test void givenNotEmptyIterable_whenSortCalled_thenItShouldReturnElementsInSortedList() { // given List elements = Arrays.asList(3, 5, 1, 4, 2); // when List sortedElements = Heap.sort(elements); // then assertThat(sortedElements).isEqualTo(Arrays.asList(1, 2, 3, 4, 5)); }

Note, that we could provide an implementation, which sorts in-place, which means we provide the result in the same array we got the elements. Additionally, this way we don't need any intermediate memory allocation. However, that implementation would be a bit harder to understand.

6. Time Complexity

Heap sort consists of two key steps, inserting an element and removing the root node. Both steps have the complexity O(log n).

Since we repeat both steps n times, the overall sorting complexity is O(n log n).

Note, that we didn't mention the cost of array reallocation, but since it's O(n), it doesn't affect the overall complexity. Also, as we mentioned before, it's possible to implement an in-place sorting, which means no array reallocation is necessary.

Also worth mentioning, that 50% of the elements are leaves, and 75% of elements are at the two bottommost levels. Therefore, most insert operations won't take more, than two steps.

Notez que sur les données réelles, Quicksort est généralement plus performant que Heap Sort. Le bon côté est que le tri en tas a toujours une complexité temporelle O (n log n) dans le pire des cas .

7. Conclusion

Dans ce didacticiel, nous avons vu une implémentation de Binary Heap et Heap Sort.

Même si sa complexité temporelle est O (n log n) , dans la plupart des cas, ce n'est pas le meilleur algorithme sur les données du monde réel.

Comme d'habitude, les exemples sont disponibles à l'adresse over sur GitHub.