Médiane du flux d'entiers utilisant Heap en Java

1. Vue d'ensemble

Dans ce didacticiel, nous allons apprendre à calculer la médiane d'un flux d'entiers.

Nous allons procéder en énonçant le problème avec des exemples, puis analyser le problème et enfin implémenter plusieurs solutions en Java.

2. Énoncé du problème

La médiane est la valeur moyenne d'un ensemble de données ordonné. Pour un ensemble d'entiers, il y a autant d'éléments inférieurs à la médiane que supérieurs.

Dans un ensemble ordonné de:

  • nombre impair d'entiers, l'élément du milieu est la médiane - dans l'ensemble ordonné {5, 7, 10} , la médiane est 7
  • nombre pair d'entiers, il n'y a pas d'élément central; la médiane est calculée comme la moyenne des deux éléments du milieu - dans l'ensemble ordonné {5, 7, 8, 10} , la médiane est (7 + 8) / 2 = 7,5

Maintenant, supposons qu'au lieu d'un ensemble fini, nous lisons des entiers d'un flux de données. Nous pouvons définir la médiane d'un flux d'entiers comme la médiane de l'ensemble des entiers lus jusqu'à présent .

Formalisons l'énoncé du problème. Étant donné une entrée d'un flux d'entiers, nous devons concevoir une classe qui effectue les deux tâches suivantes pour chaque entier que nous lisons:

  1. Ajouter l'entier à l'ensemble des entiers
  2. Trouvez la médiane des nombres entiers lus jusqu'à présent

Par exemple:

add 5 // sorted-set = { 5 }, size = 1 get median -> 5 add 7 // sorted-set = { 5, 7 }, size = 2 get median -> (5 + 7) / 2 = 6 add 10 // sorted-set = { 5, 7, 10 }, size = 3 get median -> 7 add 8 // sorted-set = { 5, 7, 8, 10 }, size = 4 get median -> (7 + 8) / 2 = 7.5 .. 

Bien que le flux ne soit pas fini, nous pouvons supposer que nous pouvons conserver tous les éléments du flux en mémoire à la fois.

Nous pouvons représenter nos tâches comme les opérations suivantes dans le code:

void add(int num); double getMedian(); 

3. Approche naïve

3.1. Liste triée

Commençons par une idée simple - nous pouvons calculer la médiane d'une liste triée d'entiers en accédant à l'élément du milieu ou aux deux éléments du milieu de la liste , par index. La complexité temporelle de l' opération getMedian est O (1) .

Lors de l'ajout d'un nouvel entier, nous devons déterminer sa position correcte dans la liste afin que la liste reste triée. Cette opération peut être effectuée en temps O (n) , où n est la taille de la liste . Ainsi, le coût global de l'ajout d'un nouvel élément à la liste et du calcul de la nouvelle médiane est O (n) .

3.2. Améliorer l'approche naïve

L' opération d' ajout s'exécute en temps linéaire, ce qui n'est pas optimal. Essayons d'aborder cela dans cette section.

Nous pouvons diviser la liste en deux listes triées - la plus petite moitié des entiers triés par ordre décroissant et la plus grande moitié des entiers par ordre croissant . Nous pouvons ajouter un nouvel entier dans la moitié appropriée de telle sorte que la taille des listes diffère de 1, au plus:

if element is smaller than min. element of larger half: insert into smaller half at appropriate index if smaller half is much bigger than larger half: remove max. element of smaller half and insert at the beginning of larger half (rebalance) else insert into larger half at appropriate index: if larger half is much bigger than smaller half: remove min. element of larger half and insert at the beginning of smaller half (rebalance) 

Maintenant, nous pouvons calculer la médiane:

if lists contain equal number of elements: median = (max. element of smaller half + min. element of larger half) / 2 else if smaller half contains more elements: median = max. element of smaller half else if larger half contains more elements: median = min. element of larger half

Bien que nous n'ayons amélioré la complexité temporelle de l' opération d' ajout que d'un facteur constant, nous avons progressé.

Analysons les éléments auxquels nous accédons dans les deux listes triées . Nous accédons potentiellement à chaque élément lorsque nous les déplaçons pendant l' opération d' ajout (triée) . Plus important encore, nous accédons respectivement au minimum et au maximum (extremums) des moitiés plus grandes et plus petites, pendant l' opération d' ajout pour le rééquilibrage et pendant l' opération getMedian .

On voit que les extremums sont les premiers éléments de leurs listes respectives . Ainsi, nous devons optimiser l'accès à l'élément à l'index 0 pour chaque moitié afin d'améliorer le temps d'exécution global de l' opération d' ajout .

4. Approche basée sur le tas

Affinons notre compréhension du problème, en appliquant ce que nous avons appris de notre approche naïve:

  1. Nous devons obtenir l'élément minimum / maximum d'un jeu de données en O (1) temps
  2. Les éléments ne doivent pas être conservés dans un ordre trié tant que nous pouvons obtenir l'élément minimum / maximum efficacement
  3. Nous devons trouver une approche pour ajouter un élément à notre ensemble de données qui coûte moins de O (n) temps

Ensuite, nous examinerons la structure de données Heap qui nous aide à atteindre nos objectifs efficacement.

4.1. Structure des données du tas

Heap est une structure de données généralement implémentée avec un tableau, mais qui peut être considérée comme un arbre binaire .

Les tas sont contraints par la propriété de tas:

4.1.1. Propriété Max - heap

Un nœud (enfant) ne peut pas avoir une valeur supérieure à celle de son parent. Par conséquent, dans un tas max , le nœud racine a toujours la plus grande valeur.

4.1.2. Min - propriété de tas

Un nœud (parent) ne peut pas avoir une valeur supérieure à celle de ses enfants. Ainsi, dans un tas min , le nœud racine a toujours la plus petite valeur.

En Java, la classe PriorityQueue représente un tas. Passons à notre première solution utilisant des tas.

4.2. Première solution

Remplaçons les listes dans notre approche naïve par deux tas:

  • Un tas min qui contient la plus grande moitié des éléments, avec l'élément minimum à la racine
  • Un tas maximum qui contient la plus petite moitié des éléments, avec l'élément maximum à la racine

Maintenant, nous pouvons ajouter l'entier entrant à la moitié pertinente en le comparant à la racine du tas min. Ensuite, si après l'insertion, la taille d'un tas diffère de celle de l'autre tas de plus de 1, on peut rééquilibrer les tas, conservant ainsi une différence de taille d'au plus 1:

if size(minHeap) > size(maxHeap) + 1: remove root element of minHeap, insert into maxHeap if size(maxHeap) > size(minHeap) + 1: remove root element of maxHeap, insert into minHeap

Avec cette approche, nous pouvons calculer la médiane comme la moyenne des éléments racines des deux tas, si la taille des deux tas est égale. Sinon, l' élément racine du tas avec plus d'éléments est la médiane .

Nous utiliserons la classe PriorityQueue pour représenter les tas. La propriété de tas par défaut d'un PriorityQueue est min-heap. Nous pouvons créer un tas max en utilisant un Comparator.reverserOrder qui utilise l'inverse de l'ordre naturel:

class MedianOfIntegerStream { private Queue minHeap, maxHeap; MedianOfIntegerStream() { minHeap = new PriorityQueue(); maxHeap = new PriorityQueue(Comparator.reverseOrder()); } void add(int num) { if (!minHeap.isEmpty() && num  minHeap.size() + 1) { minHeap.offer(maxHeap.poll()); } } else { minHeap.offer(num); if (minHeap.size() > maxHeap.size() + 1) { maxHeap.offer(minHeap.poll()); } } } double getMedian() { int median; if (minHeap.size()  maxHeap.size()) { median = minHeap.peek(); } else { median = (minHeap.peek() + maxHeap.peek()) / 2; } return median; } }

Avant d'analyser le temps d'exécution de notre code, examinons la complexité temporelle des opérations de tas que nous avons utilisées:

find-min/find-max O(1) delete-min/delete-max O(log n) insert O(log n) 

Ainsi, l' opération getMedian peut être effectuée en temps O (1) car elle ne nécessite que les fonctions find-min et find-max . La complexité temporelle de l' opération d' ajout est O (log n) - trois appels d' insertion / suppression nécessitant chacun un temps O (log n) .

4.3. Solution invariante de taille de tas

Dans notre approche précédente, nous avons comparé chaque nouvel élément avec les éléments racines des tas. Explorons une autre approche utilisant le tas dans laquelle nous pouvons tirer parti de la propriété du tas pour ajouter un nouvel élément dans la moitié appropriée.

As we have done for our previous solution, we begin with two heaps – a min-heap and a max-heap. Next, let's introduce a condition: the size of the max-heap must be (n / 2) at all times, while the size of the min-heap can be either (n / 2) or (n / 2) + 1, depending on the total number of elements in the two heaps. In other words, we can allow only the min-heap to have an extra element, when the total number of elements is odd.

With our heap size invariant, we can compute the median as the average of the root elements of both heaps, if the sizes of both heaps are (n / 2). Otherwise, the root element of the min-heap is the median.

When we add a new integer, we have two scenarios:

1. Total no. of existing elements is even size(min-heap) == size(max-heap) == (n / 2) 2. Total no. of existing elements is odd size(max-heap) == (n / 2) size(min-heap) == (n / 2) + 1 

We can maintain the invariant by adding the new element to one of the heaps and rebalancing every time:

The rebalancing works by moving the largest element from the max-heap to the min-heap, or by moving the smallest element from the min-heap to the max-heap. This way, though we're not comparing the new integer before adding it to a heap, the subsequent rebalancing ensures that we honor the underlying invariant of smaller and larger halves.

Let's implement our solution in Java using PriorityQueues:

class MedianOfIntegerStream { private Queue minHeap, maxHeap; MedianOfIntegerStream() { minHeap = new PriorityQueue(); maxHeap = new PriorityQueue(Comparator.reverseOrder()); } void add(int num) { if (minHeap.size() == maxHeap.size()) { maxHeap.offer(num); minHeap.offer(maxHeap.poll()); } else { minHeap.offer(num); maxHeap.offer(minHeap.poll()); } } double getMedian() { int median; if (minHeap.size() > maxHeap.size()) { median = minHeap.peek(); } else { median = (minHeap.peek() + maxHeap.peek()) / 2; } return median; } }

The time complexities of our operations remain unchanged: getMedian costs O(1) time, while add runs in time O(log n) with exactly the same number of operations.

Les deux solutions basées sur des tas offrent des complexités spatiales et temporelles similaires. Alors que la deuxième solution est intelligente et a une implémentation plus propre, l'approche n'est pas intuitive. D'autre part, la première solution suit naturellement notre intuition, et il est plus facile de raisonner sur l'exactitude de son opération d' ajout .

5. Conclusion

Dans ce didacticiel, nous avons appris à calculer la médiane d'un flux d'entiers. Nous avons évalué quelques approches et implémenté quelques solutions différentes en Java à l'aide de PriorityQueue .

Comme d'habitude, le code source de tous les exemples est disponible à l'adresse over sur GitHub.