Diferencia entre std::set y std::priority_queue

Question 1

Ya que ambos 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 uno u 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 sus actuación y idoneidad para varios usos.

Nota: Sé acerca de los no-duplicados en un conjunto. Por eso también mencioné std::multiset ya que tiene exactamente el mismo comportamiento que el std::set pero se puede usar cuando los datos almacenados se pueden comparar como elementos iguales. Así que, por favor, no comentes sobre el problema de una o varias teclas.

Question 2

Una cola prioritaria solamente te da acceso a una elemento en orden ordenado, es decir, puede obtener el elemento de mayor prioridad y, cuando lo elimine, puede obtener la siguiente prioridad más alta, y así sucesivamente. Una cola de prioridad también permite elementos duplicados, por lo que se parece más a un conjunto múltiple que a un conjunto. [Edit: As @Tadeusz Kopec pointed out, building a heap is also linear on the number of items in the heap, where building a set is O(N log N) unless it’s being built from a sequence that’s already ordered (in which case it is also linear).]

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 atravesar en orden de uno a otro.

Question 3

std::priority_queue permite hacer lo siguiente:

Insertar un elemento O(log n)
Consigue el pequeñísimo elemento O(1)
borrar el pequeñísimo elemento O(log n)

tiempo std::set tiene más posibilidades:

Insertar cualquier elemento O(log n) y la constante es mayor que en std::priority_queue
Encontrar ningún elemento O(log n)
Encuentre un elemento, >= que el que está buscando O(log n) (lower_bound)
Borrar ningún elemento O(log n)
Borrar ningún elemento por su iterator O(1)
Mover al elemento anterior/siguiente en orden ordenado O(1)
Consigue el pequeñísimo elemento O(1)
Consigue el más grande elemento O(1)

Question 4

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_(estructura_de_datos)

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

Ambas estructuras están dispuestas 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

En un montón P

Entonces, los árboles binarios se clasifican “hacia los lados” y los montones se clasifican “hacia arriba”.

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

Esto tiene los siguientes efectos:

Si tiene una matriz desordenada y quiere convertirla en un árbol binario, se necesita O(nlogn) tiempo. Si quieres convertirlo en un montón, solo necesitas 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 (el más bajo o el 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 mantener la colección completa ordenada todo el tiempo.
Los montones tienen una búsqueda en tiempo constante (vistazo) del elemento más bajo, los árboles binarios tienen una búsqueda en tiempo logarítmico del elemento más bajo.

¿Ha sido útil esta solución?