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

Priority_queue es un contenedor adaptador, lo que significa que se aplica en la parte superior de algunos subyacente tipo de contenedor. Por defecto subyacente es de tipo vector, pero de un tipo diferente puede ser seleccionado de forma explícita.

y

Colas de prioridad son un concepto estándar, y puede ser implementado de diferentes maneras, de esta implementación utiliza montones.

Anteriormente había supone que top() es O(1), y que push() sería un O(logn) (las dos razones por las que eligió el priority_queue en el primer lugar) -, pero la documentación ni confirma ni desmiente esta hipótesis.

A cavar más profundo, la documentación de la Secuencia concepto de decir:

Las complejidades de un solo elemento a insertar y borrar secuencia dependiente.

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

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

Estoy inferir que, utilizando el valor predeterminado 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: Iba a ser capaz de lograr O(logn) eficiencia en push() si he utilizado un set (o multiset) en lugar de un vector para la aplicación de la priority_queue? Cuáles serían las consecuencias de hacer esto? ¿Qué otras operaciones sufrir como consecuencia?

N. B.: estoy preocupado por el ahorro de tiempo aquí, no el espacio.

6 Comentarios

  1. 33

    La cola de prioridad adaptador utiliza la biblioteca estándar montón de algoritmos para generar y acceder a la cola, es la complejidad de los algoritmos que usted debe buscar en la documentación.

    La parte superior (a) la operación es, obviamente, O(1), pero es de suponer que usted desea pop() de la pila después de llamar a lo que (según Josuttis) es O(2*log(N)) y push() es O(log(N)) – la misma fuente.

    Y desde el Estándar de C++, 25.6.3.1, push_heap :

    Complejidad: En la mayoría de los registro(apellidos) comparaciones.

    y pop_heap:

    Complejidad: En la mayoría de los 2 * log(apellidos) comparaciones.

  2. 6

    top() – O(1) –, ya que sólo devuelve el elemento @ frontal.

    push()

    • inserto en el vector 0(1) amortizado
    • push_into_heap – En la mayoría de log(n) comparaciones. O(logn)

      de modo push() la complejidad es —
      log(n)

  3. 5

    No. Esto no es correcto. parte superior() es O(1) y presione() es O(log n). Leer la nota 2 en la documentación para ver que este adaptador no permiten recorrer el vector. Neil está en lo correcto acerca de pop(), pero todavía esto permite trabajar con el montón haciendo inserciones y eliminaciones en O(log n) tiempo.

  4. 2

    Si la estructura de datos subyacente es un montón, la parte superior() será constante en el tiempo, y push (EDIT: y pop) será logarítmica (como usted dice). El vector es utilizado para almacenar estas cosas como esta:

    MONTÓN:

                 1

            2         3

          8 12   11 9

    VECTOR (utilizado para almacenar)

    1 2 3 8 12 11 9

    Usted puede pensar en él como el elemento en la posición i niños (2i) y (2i+1)

    Que utilizar el vector porque almacena los datos de forma secuencial (que es mucho más eficiente y caches de la discreta)

    Independientemente de cómo se almacena un montón siempre debe ser implementada (especialmente por los dioses que hizo la ETS lib), de modo que el pop es constante y empuje es logarítmica

    • Esto no funciona de esa manera: pop() reordena el vector para mantener el montón de la propiedad, y por lo tanto es O(log n).
    • En realidad, es todo lo contrario – la divina montones push O(1), pero pop O(log n).
    • Cómo puede empujar O(1). Si el nuevo elemento debe convertirse en el nuevo o la nueva parte inferior, posiblemente, pero si se necesita ir a algún lugar en el medio tendrás que llamar a la actualización de un montón de O(lg n) de la función.
    • peek() es O(1), pop() es O(log(N)), como es push().
  5. 2

    C++ STL priority_queue estructura de datos subyacente es el Montón de la estructura de los datos(Heap es una no lineal de ADT que se basa en la completa árbol binario y binario completo árbol se implementa a través de vector(o Matriz) de contenedor.

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

    P1: no me fijé en el estándar, pero AFAIK, utilizando vector (o deque por cierto), la complejidad sería O(1) para top(), O(log n) para push() y pop(). Yo una vez en comparación std::priority_queue con mi propia montón con O(1) push() y top() y O(log n) pop() y ciertamente, no era tan lento como O(n).

    P2: set no es utilizable como subyacente contenedor para priority_queue (no una Secuencia), pero sería posible usar set para implementar una cola de prioridad con O(log n) push() y pop(). Sin embargo, esto no sería probablemente superan a los std::priority_queue más de std::vector aplicación.

    • ¿tienes código para una operación O(1) la inserción?
    • Lo lenta que era STL PQ en comparación con su aplicación?

Dejar respuesta

Please enter your comment!
Please enter your name here