Implémenter une file d'attente dans laquelle push_rear (), pop_front () et get_min () sont toutes des opérations à temps constant

Question

Je suis tombé sur cette question: Mettre en œuvre une file d'attente dans laquelle push_rear(), pop_front() et get_min() sont tous de la constante de temps des opérations.

J'ai d'abord pensé à utiliser un min-tas structure de données qui a O(1) de complexité pour un get_min(). Mais push_rear() et pop_front() serait en O(log(n)).

Personne ne sait ce qui serait la meilleure façon de mettre en œuvre une telle file d'attente qui a O(1) push(), pop() et min()?

J'ai googlé à ce sujet, et je voulais souligner cet Algorithme Geeks fil. Mais il semble qu'aucune des solutions de suivi de la constante de temps de la règle pour l'ensemble des 3 méthodes: push(), pop() et min().

Merci pour toutes les suggestions.

Answer 1

Vous pouvez implémenter une pile avec O(1) pop(), push() et get_min(): il suffit de stocker le minimum actuel avec chaque élément. Ainsi, par exemple, la pile [4,2,5,1] (1 sur le dessus) devient [(4,4), (2,2), (5,2), (1,1)].

Ensuite, vous pouvez utiliser deux piles de mettre en œuvre la file d'attente. Pousser à une pile, de la pop à partir d'un autre; si la deuxième pile est vide au cours de la pop, de déplacer tous les éléments de la première pile à la seconde.

E. g pour un pop la demande, de déplacer tous les éléments de la première pile [(4,4), (2,2), (5,2), (1,1)], la deuxième pile serait [(1,1), (5,1), (2,1), (4,1)]. et maintenant, retour haut de l'élément à partir de la deuxième pile.

Pour trouver le minimum de l'élément de la file d'attente, regarder le plus petit des deux éléments de l'individu min-piles, puis prendre le minimum de ces deux valeurs. (Bien sûr, il y a une certaine logique supplémentaire ici est cas l'une des piles est vide, mais ce n'est pas trop dur à contourner).

Il aura O(1) get_min() et push() et amorti O(1) pop().

Answer 2

Pas grave je pense que j'ai une réponse qui vous donne toutes ces opérations dans amorti O(1), ce qui signifie que toute une opération pourrait prendre jusqu'à O(n), mais n'importe quelle séquence de n opérations prend O(1) fois par opération.

L'idée est de stocker vos données dans un arbre Cartésien. C'est un arbre binaire obéissant à de la min-propriété tas (chaque nœud est pas plus grand que ses enfants), et est commandé de telle façon qu'un afinde de la traversée de l'nœuds permet les nœuds dans le même ordre dans lequel ils ont été ajoutés. Pour exemple, voici un Cartésien de l'arbre de la séquence de 2 1 4 3 5:

       1
     /   \
    2      3
          / \
         4   5

Il est possible d'insérer un élément dans un arbre Cartésien en O(1) amorti temps à l'aide de la procédure suivante. Regardez la tranche droite de l'arbre (le chemin de la racine à la droite de la feuille formée par toujours marchant vers la droite). Départ à droite du nœud, balayez vers le haut le long de ce chemin jusqu'à ce que vous trouver le premier noeud plus petit que le nœud de l'insertion.
Changement de nœud, de sorte que son droit est cet enfant nouveau nœud, puis assurez-vous que le nœud de l'ancien droit de l'enfant à la gauche de l'enfant du nœud que vous venez d'ajouter. Par exemple, supposons que nous voulons insérer une autre copie de 2) dans le dessus de l'arbre. Nous marchons jusqu'à la droite de la colonne vertébrale passé le 5 et le 3, mais stop au-dessous de la 1 car 1 < 2. Nous avons ensuite changer l'arbre à ressembler à ceci:

       1
     /   \
    2      2
          /
         3
        / \
       4   5

Notez qu'une afinde traversée donne 2 1 4 3 5 2, qui est la séquence dans laquelle nous avons ajouté les valeurs.

Cela va dans amorti O(1) car il peut créer une fonction de potentiel égal au nombre de nœuds dans la tranche droite de l'arbre. Le temps réel nécessaire pour insérer un nœud est de 1, plus le nombre de nœuds dans la colonne vertébrale, nous considérons (appelons k). Une fois que nous trouvons de la place pour insérer le nœud, la taille de la colonne vertébrale se rétrécit en fonction de la longueur k - 1, puisque chacune des k nœuds que nous avons visités ne sont plus sur le droit de la colonne vertébrale, et le nouveau nœud est à sa place. Cela donne un coût amorti de 1 + k + (1 - k) = 2 = O(1), pour l'amorti O(1) insérer. Une autre façon de penser à ce sujet, une fois qu'un nœud a été déplacé de la droite de la colonne vertébrale, il n'est jamais partie de la tranche droite de nouveau, et ainsi nous n'aurons jamais à se déplacer à nouveau. Depuis chacune des n nœuds peut être déplacé plus d'une fois, cela signifie que n insertions peuvent le faire au plus n se déplace, de sorte que le total d'exécution est au plus O(n) pour un amorti O(1) par élément.

Pour faire une résorption de l'étape, on enlève simplement la plus à gauche du nœud de l'arbre Cartésien. Si ce nœud est une feuille, nous avons terminé. Sinon, le nœud peut avoir qu'un seul enfant (l'enfant), et nous avons donc remplacer le noeud avec son enfant. À condition de garder une trace de l'endroit où le nœud le plus à gauche est, cette étape prend O(1) fois. Cependant, après la suppression de la plus à gauche du nœud et de la remplacer par son droit à l'enfant, nous pourrions ne pas savoir où le nouveau nœud le plus à gauche est. Pour résoudre ce problème, nous avons tout simplement marcher sur le côté gauche de la colonne vertébrale de l'arbre de départ au nouveau nœud on a juste déplacé vers l'extrême gauche de l'enfant. Je demande que cela s'exécute en O(1) amorti temps. Pour voir cela, j'affirme qu'un nœud est visité plus d'une fois au cours de l'une de ces passes pour trouver le nœud le plus à gauche. Pour voir cela, notez qu'une fois qu'un nœud a reçu la visite de cette façon, la seule façon que nous pourrions avoir besoin de le regarder de nouveau, serait si elle ont été déplacées d'un enfant de la plus à gauche du nœud le plus à gauche du nœud. Mais tous les nœuds visités sont les parents de la plus à gauche du nœud, de sorte que cela ne se peut. Par conséquent, chaque nœud est visité plus d'une fois au cours de ce processus, et de la pop s'exécute en O(1).

Nous pouvons faire trouver-min en O(1) car la rupture Cartésienne de l'arbre nous donne accès à la plus petit élément de l'arborescence pour gratuits; c'est la racine de l'arbre.

Enfin, pour voir que les nœuds de revenir dans le même ordre dans lequel ils ont été insérés, notez qu'un Cartésien arbre stocke ses éléments, de sorte qu'un afinde traversée de visites dans l'ordre de tri. Depuis que nous avons toujours supprimer le nœud le plus à gauche à chaque étape, et c'est le premier élément de la afinde de la traversée, nous avons toujours obtenir les nœuds dans l'ordre dans lequel ils ont été insérés.

En bref, nous obtenons O(1) amorti push et pop, et O(1) le pire des cas, trouvez-min.

Si je peut venir avec un pire cas O(1) mise en œuvre, je vais certainement poster. Ce fut un grand problème; merci de poster!

Answer 3

Ok, voici une solution.

Nous avons d'abord besoin de quelques trucs qui fournissent push_back(),push_front(),pop_back() et pop_front() 0(1). Il est facile à mettre en œuvre avec table et 2 itérateurs. Première itérateur qui pointe vers l'avant, la seconde à l'arrière. Nous allons appeler ces choses deque.

Voici un pseudo-code:

class MyQueue//Our data structure
{
    deque D;//We need 2 deque objects
    deque Min;

    push(element)//pushing element to MyQueue
    {
        D.push_back(element);
        while(Min.is_not_empty() and Min.back()>element)
             Min.pop_back();
        Min.push_back(element);
    }
    pop()//poping MyQueue
    {
         if(Min.front()==D.front() )
            Min.pop_front();
         D.pop_front();
    }

    min()
    {
         return Min.front();
    }
}

Explication:

Exemple, nous allons pousser les numéros [12,5,10,7,11,19] et à notre MyQueue

1)pousser 12

D [12]
Min[12]

2)pousser 5

D[12,5]
Min[5] //5>12 so 12 removed

3)pousser 10

D[12,5,10]
Min[5,10]

4)en poussant 7

D[12,5,10,7]
Min[5,7]

6)en poussant 11

D[12,5,10,7,11]
Min[5,7,11]

7)en poussant 19

D[12,5,10,7,11,19]
Min[5,7,11,19]

Maintenant, nous allons appeler pop_front()

nous avons eu

 D[5,10,7,11,19]
 Min[5,7,11,19]

Le minimum est de 5

Appelons pop_front() à nouveau

Explication: pop_front va supprimer 5 de D, mais il affichera l'élément avant de Min trop, car il est égal à D de l'élément avant (5).

 D[10,7,11,19]
 Min[7,11,19]

Et le minimum est de 7. :)

Answer 4

Utiliser un deque (A) pour stocker les éléments et un autre deque (B) pour stocker le minimum.

Lorsque x est mis en file d'attente, push_back à Un et garder pop_backing B jusqu'à ce que le retour de B est plus petit que x, alors push_back x pour B.

lorsque la file d'attente A, pop_front Un comme valeur de retour, et si elle est égale à la face B, pop_front B ainsi.

lors de l'obtention du minimum de Un, utilisez le devant de B comme valeur de retour.

retirer et à getmin sont évidemment O(1). Pour la mise en file d'exploitation, tenez compte de la push_back de n éléments. Il y a n push_back à Un, n push_back à B et à plus n pop_back de B parce que chaque élément soit rester dans B ou sauté une fois de B. en Plus de tout, il y a O(3n) opérations et, par conséquent, le coût amorti est O(1) ainsi que pour la mise en file d'attente.

Enfin la raison de cet algorithme fonctionne, c'est que lorsque vous mettre en file d'attente x de A, si il y a des éléments de B qui sont plus grand que x, ils ne seront jamais minimums maintenant, parce que x va rester dans la file d'attente plus longtemps que tous les éléments de B (une file d'attente FIFO). Donc nous avons besoin de sortir des éléments de B (de l'arrière) qui sont plus grands que x avant de nous appuyer sur x dans B.

from collections import deque


class MinQueue(deque):
    def __init__(self):
        deque.__init__(self)
        self.minq = deque()

    def push_rear(self, x):
        self.append(x)
        while len(self.minq) > 0 and self.minq[-1] > x:
            self.minq.pop()
        self.minq.append(x)

    def pop_front(self):
        x = self.popleft()
        if self.minq[0] == x:
            self.minq.popleft()
        return(x)

    def get_min(self):
        return(self.minq[0])

Answer 5

Si vous n'avez pas l'esprit de stockage d'un bit de données supplémentaires, il devrait être assez simple pour stocker la valeur minimale. Push et pop pouvez mettre à jour la valeur si le nouveau ou l'élément supprimé est le minimum, et le retour à la valeur minimale est aussi simple que d'obtenir la valeur de la variable.

C'est en supposant que get_min() ne modifie pas les données; si vous préférez quelque chose comme pop_min() (c'est à dire supprimer l'élément minimum), vous pouvez facilement stocker un pointeur vers l'élément actuel et l'élément qui le précède (le cas échéant), et de mettre à jour ceux en conséquence avec push_rear() et pop_front ().

Edit après les commentaires:

Évidemment, cela conduit à O(n) push et pop dans le cas où le minimum de modifications sur ces opérations, et n'a donc pas strictement satisfaire aux exigences.