c++ - geeksforgeeks - Diferencia entre std:: set y std:: priority_queue

queue c++ geeksforgeeks

Question

Dado que std::priority_queue y std::set (y std::multiset ) son contenedores de datos que almacenan elementos y le permiten acceder a ellos de manera ordenada, y tienen la misma complejidad de inserción O(log n) , ¿cuáles son las ventajas? de usar uno sobre el otro (o, ¿qué tipo de situaciones requieren el uno o el otro?)?

Si bien sé que las estructuras subyacentes son diferentes, no estoy tan interesado en la diferencia en su implementación como en la comparación de su rendimiento e idoneidad para diversos usos.

Nota: Sé acerca de los no duplicados en un conjunto. Es por eso que también mencioné std::multiset ya que tiene exactamente el mismo comportamiento que std::set pero puede usarse donde los datos almacenados se pueden comparar como elementos iguales. Así que, por favor, no comente sobre el problema de teclas simples / múltiples.

Answer 1

Dado que std::priority_queue y std::set (y std::multiset ) son contenedores de datos que almacenan elementos y le permiten acceder a ellos de manera ordenada, y tienen la misma complejidad de inserción O(log n) , ¿cuáles son las ventajas? de usar uno sobre el otro (o, ¿qué tipo de situaciones requieren el uno o el otro?)?

Aunque las operaciones de inserción y borrado para ambos contenedores tienen la misma complejidad O (log n) , estas operaciones para std::set son más lentas que para std::priority_queue . Esto se debe a que std::set realiza muchas asignaciones de memoria. Cada elemento de std::set se almacena en su propia asignación. std::priority_queue (con el contenedor std::vector subyacente por defecto) utiliza una asignación única para almacenar todos los elementos. Por otro lado, std::priority_queue usa muchas operaciones de intercambio en sus elementos, mientras que std::set usa solo intercambio de punteros. Entonces, si el intercambio es una operación muy lenta para el tipo de elemento, el uso de std::set puede ser más eficiente. Además, el elemento puede no ser intercambiable en absoluto.

La sobrecarga de memoria para std::set es mucho más grande también porque tiene que almacenar muchos punteros entre sus nodos.

Answer 2

Una cola de prioridad solo le da acceso a un elemento en orden ordenado, es decir, puede obtener el elemento de mayor prioridad, y cuando lo elimina, puede obtener la siguiente prioridad más alta, y así sucesivamente. Una cola prioritaria también permite elementos duplicados, por lo que se parece más a un conjunto múltiple que a un conjunto. [Editar: como señaló @Tadeusz Kopec, construir un montón también es lineal en la cantidad de elementos en el montón, donde construir un conjunto es O (N log N) a menos que se construya a partir de una secuencia que ya está ordenada (en cuyo caso también es lineal).]

Un conjunto le permite acceso completo en orden ordenado, por lo que puede, por ejemplo, encontrar dos elementos en algún lugar en el medio del conjunto y luego recorrer en orden de uno a otro.

Answer 3

set / multiset generalmente están respaldados por un árbol binario. http://en.wikipedia.org/wiki/Binary_tree

priority_queue generalmente está respaldado por un montón. http://en.wikipedia.org/wiki/Heap_(data_structure)

Entonces, la pregunta es realmente cuándo debería usar un árbol binario en lugar de un montón.

Ambas estructuras se presentan en un árbol, sin embargo, las reglas sobre la relación entre los antepasados ​​son diferentes.

Llamaremos a las posiciones P para padre, L para hijo izquierdo y R para hijo derecho.

En un árbol binario L <P <R.

En un montón P <L y P <R

Entonces los árboles binarios se clasifican "de lado" y los montones se clasifican "hacia arriba".

Entonces, si consideramos esto como un triángulo que en el árbol binario L, P, R están completamente ordenados, mientras que en el montón la relación entre L y R es desconocida (solo su relación con P).

Esto tiene los siguientes efectos:

• Si tiene una matriz no ordenada y desea convertirla en un árbol binario, toma tiempo O(nlogn) . Si desea convertirlo en un montón, solo toma O(n) tiempo, (ya que solo se compara para encontrar el elemento extremo)

• Los montones son más eficientes si solo necesita el elemento extremo (más bajo o más alto según alguna función de comparación). Los montones solo hacen las comparaciones (perezosamente) necesarias para determinar el elemento extremo.

• Los árboles binarios realizan las comparaciones necesarias para ordenar la colección completa, y mantienen la colección completa ordenada todo el tiempo.

• Los montones tienen una búsqueda de tiempo constante (vistazo) del elemento más bajo, los árboles binarios tienen una búsqueda de tiempo logarítmico del elemento más bajo.

Answer 4

std::priority_queue permite hacer lo siguiente:

1. Insertar un elemento O(log n)
2. Obtenga el elemento más pequeño O(1)
3. Borrar el elemento más pequeño O(log n)

mientras que std::set tiene más posibilidades:

1. Inserte cualquier elemento O(log n) y la constante es mayor que en std::priority_queue
2. Encuentra cualquier elemento O(log n)
3. Encuentre un elemento,> = que el que está buscando O(log n) ( lower_bound )
4. Borrar cualquier elemento O(log n)
5. Borrar cualquier elemento por su iterator O(1)
6. Mover al elemento anterior / siguiente en orden ordenado O(1)
7. Obtenga el elemento más pequeño O(1)
8. Obtenga el elemento más grande O(1)