geeksforgeeks - stl c++ priority queue

Eficiencia de la prioridad de STL

Question

Tengo una aplicación (C ++) que creo que estaría bien atendida por una priority_queue STL. La documentación dice:

Priority_queue es un adaptador de contenedor, lo que significa que se implementa sobre algún tipo de contenedor subyacente. Por defecto, el tipo subyacente es vector, pero se puede seleccionar un tipo diferente explícitamente.

y

Las colas de prioridad son un concepto estándar y se pueden implementar de muchas maneras diferentes; esta implementación usa montones.

Anteriormente había asumido que top() es O(1) , y que push() sería una O(logn) (las dos razones por las que elegí la priority_queue en primer lugar), pero la documentación no confirma ni niega esta suposición.

Profundizando más, los documentos para el concepto de Secuencia dicen:

Las complejidades de la inserción y borrado de un solo elemento dependen de la secuencia.

La priority_queue usa un vector (por defecto) como un montón, que:

... admite el acceso aleatorio a los elementos, la inserción de tiempo constante y la eliminación de elementos al final, y la inserción de tiempo lineal y la eliminación de elementos al principio o en el medio.

Debo inferir que, usando la priority_queue , top() es O(1) y push() es O(n) .

Pregunta 1: ¿Es esto correcto? ( top() acceso es O(1) y push() es O(n) ?

Pregunta 2: ¿Sería capaz de lograr la eficiencia O(logn) en push() si utilicé un set (o multiset ) en lugar de un vector para la implementación de la priority_queue ? ¿Cuáles serían las consecuencias de hacer esto? ¿Qué otras operaciones sufrirían como consecuencia?

NB: me preocupa la eficiencia del tiempo aquí, no el espacio.

Answer 1

El adaptador de cola de prioridad usa los algoritmos de montón de biblioteca estándar para construir y acceder a la cola; es la complejidad de los algoritmos que debe buscar en la documentación.

La operación top () es obviamente O (1) pero presumiblemente quiere pop () el montón después de llamarlo que (de acuerdo con Josuttis ) es O (2 * log (N)) y push () es O (log (N )) - la misma fuente.

Y del estándar C ++, 25.6.3.1, push_heap:

Complejidad: en la mayoría de las comparaciones log (last - first).

y pop_heap:

Complejidad: como máximo, 2 * log (últimas) primeras comparaciones.

Answer 2

La estructura de datos subyacente de C ++ STL priority_queue es la estructura de datos Heap (Heap es un ADT no lineal que se basa en un árbol binario completo y un árbol binario completo a través del contenedor vectorial (o Array).

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).

Answer 3

No esto no es correcto. top () es O (1) y push () es O (log n). Lea la nota 2 en la documentación para ver que este adaptador no permite iterar a través del vector. Neil tiene razón sobre pop (), pero aún así esto permite trabajar con el montón haciendo inserciones y eliminaciones en el tiempo O (log n).

Answer 4

Q1: No miré en el estándar, pero AFAIK, usando el vector (o deque btw), la complejidad sería O(1) para top() , O(log n) para push() y pop() . Una vez std::priority_queue con mi propio montón con O(1) push() y top() y O(log n) pop() y ciertamente no fue tan lento como O(n) .

Q2: set no se puede utilizar como contenedor subyacente para priority_queue (no es una secuencia), pero sería posible usar set para implementar una cola de prioridad con O(log n) push() y pop() . Sin embargo, esto probablemente no supere la implementación de std::priority_queue sobre std::vector .

Answer 5

Si la estructura de datos subyacente es un montón, top () será un tiempo constante, y push (EDIT: y pop) será logarítmico (como usted dice). El vector solo se usa para almacenar estas cosas de esta manera:

MONTÓN:
1
2 3
8 12 11 9

VECTOR (usado para almacenar)

1 2 3 8 12 11 9

Puedes pensarlo ya que el elemento en los hijos de la posición i es (2i) y (2i + 1)

Usan el vector porque almacena los datos secuencialmente (que es mucho más eficiente y menos caché que discreto)

Independientemente de cómo se almacena, siempre se debe implementar un montón (especialmente por los dioses que crearon la lib de STD) para que el pop sea constante y el empuje sea logarítmico

Answer 6

top() - O (1) - ya que simplemente devuelve el elemento @ front.

push() -

• insertar en el vector - 0 (1) amortizado

• push_into_heap - Como máximo, log (n) comparaciones. O (logn)

  la complejidad de push () es - log (n)