Implémentation de la recherche du plus grand et des n/3 plus grands éléments

Question

Supposons que vous recevez des nombres tout le temps et que vous ne savez pas combien de nombres vont arriver au début. A tout moment, je veux pouvoir sortir le plus grand nombre et le plus petit nombre. n/3 le plus grand nombre (où n est le nombre de chiffres saisis jusqu'à ce point) immédiatement (in O(1)) . Le temps maximum pour la saisie de nouveaux numéros est de O(log(n)) .

Quelle est la meilleure façon de mettre en œuvre ce système ?

Answer 1

Vous pourriez l'implémenter avec deux amas : un mini-heap (A), et un max-heap (B).

L'idée est de stocker dans A les n/3 les plus grandes valeurs, et le reste en B de sorte que le maximum en B soit le n/3 la plus grande valeur (en comptant à partir de zéro). En supposant que n/3 est tronquée au cas où n n'est pas un multiple de trois, et que la valeur résultante est basée sur zéro ( n/3 == 0 signifie que le maximum est aussi le n/3 plus grand élément), cela signifie que l'invariance suivante doit être maintenue :

A.size == floor((A.size + B.size)/3)

...ce qui revient à dire :

0 <= B.size - 2*A.size < 3 

La condition ci-dessus peut varier un peu en fonction de l'interprétation que l'on fait de ce que l'on appelle l'objectif de l'UE. n/3 (est-il basé sur 0, 1, arrondi, tronqué,...), et une attention particulière peut être nécessaire lorsqu'il y a moins de 3 éléments dans la collection totale, en fonction de cette définition.

Pour ajouter une valeur v vous devez d'abord décider dans quel tas il appartient. S'il est plus petit que l'actuel n/3 th la plus grande valeur -- la valeur maximale en B -- alors elle appartient à B, sinon à A. Après cet ajout, l'invariance peut être rompue et doit être restaurée en retirant une valeur de l'un des tas et en l'ajoutant à l'autre.

Plus formellement v est ajouté comme suit :

if v < B.peek():
    B.add(v)
    if B.size - 2*A.size >= 3:
        A.add(B.pull())
else:
    A.add(v)
    if B.size - 2*A.size < 0:
        B.add(A.pull())

L'implémentation pour obtenir le n/3 th la plus grande valeur serait :

B.peek()

La complexité temporelle des méthodes utilisées ci-dessus est la suivante :

• taille : O(1)
• poire : O(1)
• tirer : O(logn)
• ajouter : O(logn)

Maintenir le maximum global est une tâche facile. Les tas ne servent qu'à garder la trace des n/3 th la plus grande valeur.