L'efficacité de la STL priority_queue

J'ai une application (C++) que je pense que ce serait bien servi par un STL priority_queue. La documentation dit:

Priority_queue est un conteneur de l'adaptateur, ce qui signifie qu'il est mis en œuvre sur le dessus de certaines sous-jacent type de conteneur. Par défaut que le type sous-jacent est un vecteur, mais un type différent peut être sélectionné de manière explicite.

Files d'attente de priorité sont un concept standard, et peut être mis en œuvre dans de nombreuses façons différentes; cette implémentation utilise des tas.

J'avais déjà supposé que top() est O(1), et que push() serait un O(logn) (les deux raisons que j'ai choisi le priority_queue en premier lieu), mais la documentation ne confirme ni ne réfute cette hypothèse.

Creuser plus profond, les docs pour la Séquence concept de dire:

La complexité de l'élément unique d'insertion et d'effacement sont la séquence dépendante.

La priority_queue utilise un vector (par défaut) comme un tas, dont:

... prend en charge l'accès aléatoire à des éléments, de la constante de temps de l'insertion et de suppression d'éléments à la fin, et le temps linéaire de l'insertion et de suppression d'éléments au début ou au milieu.

Je suis en déduire que, à l'aide de la valeur par défaut priority_queue, top() est O(1) et push() est O(n).

Question 1: Est-ce correct? (top() accès est O(1) et push() est O(n)?)

Question 2: serais-je capable d'atteindre O(logn) efficacité sur push() si j'ai utilisé une set (ou multiset) au lieu d'un vector pour la mise en œuvre de la priority_queue? Quelles seraient les conséquences de cette mesure? Quelles sont les autres activités qui souffrent comme une conséquence?

N. B.: je suis inquiet à propos de l'efficacité dans le temps, ici, non pas de l'espace.

InformationsquelleAutor Chris Tonkinson | 2010-06-04

c++data-structures performance priority-queue stl

33

La file d'attente de priorité de l'adaptateur utilise la bibliothèque standard tas algorithmes afin de créer et accéder à la file d'attente, c'est la complexité de ces algorithmes, vous devriez être à la recherche dans la documentation.

Le haut() l'opération est évidemment O(1), mais sans doute que vous souhaitez pop() le tas après l'appel à elle qui (selon Josuttis) est O(2*log(N)) et poussez-la() est O(log(N)) - de même source.

Et de la Norme C++, 25.6.3.1, push_heap :

Complexité: À la plupart des journaux(le dernier - premier) comparaisons.

et pop_heap:

Complexité: Au maximum 2 * log(dernier - premier) comparaisons.

InformationsquelleAutor
5

Pas. Ce n'est pas correct. top() est O(1) et poussez-la() est O(log n). Lire la note 2 dans la documentation de voir que cette carte ne permet pas de l'itération par le vecteur. Neil est correct sur les pop(), mais cela permet de travailler avec les tas de faire des insertions et des suppressions en O(log n) fois.

InformationsquelleAutor Yuval F
5

top() - O(1), comme elle retourne l'élément @ avant.

push() -
- insérer dans le vecteur - 0(1) amorti
- push_into_heap - tout Au plus log(n) comparaisons. O(logn)
  
  donc push() la complexité est --
  log(n)
InformationsquelleAutor aJ.
2

Si les données sous-jacentes de la structure est un segment, haut() sera constante de temps, et push (EDIT: et pop) sera logarithmique (comme vous dites). Le vecteur est seulement utilisé pour stocker ces choses comme ceci:

TAS:

             1

        2         3

      8 12 11 9

VECTEUR (utilisé pour stocker)

1 2 3 8 12 11 9

Vous pouvez la considérer comme l'élément à la position i enfants (2i) et (2i+1)

Ils utilisent le vecteur car il stocke les données de manière séquentielle (qui est beaucoup plus efficace et cache-friendly que discret)

Indépendamment de la façon dont il est stocké, un tas doit toujours être mis en œuvre (en particulier par les dieux qui ont fait le STD lib), de sorte que le bruit est constant et le push est logarithmique
- Cela ne fonctionne pas de cette façon: pop() trie le vecteur pour maintenir la propriété tas, et il est donc en O(log n).
- En fait, c'est tout le contraire - le divin tas de " push O(1), mais pop O(log n).
- Comment peuvent pousser à être O(1). Si le nouvel élément doit devenir le nouveau haut ou le nouveau fond peut-être, mais si elle a besoin d'aller quelque part dans le milieu, vous aurez besoin de demander la mise à jour de tas un O(lg n) de la fonction.
- peek() est O(1), mais de la pop() est O(log(N)), comme c'est push().
InformationsquelleAutor Bob Fincheimer

C++ STL priority_queue de données sous-jacente de la structure est de Segment de structure de données(Segment est un non linéaire de l'ADT qui, sur base binaire complet de l'arbre et de l'arbre binaire complet est mis en œuvre par le vecteur(ou un Tableau) du conteneur.

ex  Input data : 5 9 3 10 12 4.

Heap (Considering Min heap) would be :

                   [3]
             [9]             [4]
         [10]    [12]     [5]


   NOW , we store this min heap in to vector,             
      [3][9][4][10][12][5].
      Using formula ,
      Parent : ceiling of n-1/2
      Left Child : 2n+1
      Right Child : 2n+2 .
  Hence ,
    Time Complexity for 
             Top = O(1) , get element from root node.
             POP()= O(logn) , During deletion of root node ,there  is      chance to violation of  heap order . hence restructure of heap order takes at most O(logn) time (an element might move down to height of tree).
            PUSH()= O(logn) , During insertion also , there might chance to violation of  heap order . hence restructure of heap order takes at most O(logn) time (an element might move up to root from leaf node).

InformationsquelleAutor YADAV

1

Q1: je ne l'ai pas dans la norme, mais autant que je sache, à l'aide de vector (ou deque btw), la complexité serait O(1) pour top(), O(log n) pour push() et pop(). Une fois, j'ai comparé std::priority_queue avec mon propre tas avec O(1) push() et top() et O(log n) pop() et ce n'était certainement pas aussi lent que O(n).

T2: set est pas utilisable en tant que conteneur sous-jacent pour priority_queue (pas un ordre), mais il serait possible d'utiliser pour implémenter une file d'attente de priorité avec O(log n) push() et pop(). Toutefois, cela ne serait probablement pas surpasser la std::priority_queue sur std::vector mise en œuvre.
- avez-vous de code pour un O(1) push?
- La lenteur a été STL PQ par rapport à votre mise en œuvre?
InformationsquelleAutor jpalecek

Vous devez vous connecter pour publier un commentaire.