10
¿Cómo puedo configurar std::priority_queue para ignorar los duplicados?¿Cómo puedo configurar std :: priority_queue para ignorar los duplicados?
Cuando agrego una clave que ya está contenida, esta nueva debe ignorarse. (En mi caso, la prioridad para el viejo y el nuevo que siempre será exactamente el mismo.)
complejidad en cuanto a que no debe hacer una diferencia: Se tratará de insertar en el lugar adecuado, encontrar la existente allí y no hacer nada. La pregunta es si std::priority_queue es configurable de esa manera.
No creo que un montón apoya "encontrar una ya existente" en O (log N). – kennytm
@KennyTM, afortunadamente, el pqueue no tiene que ser un montón ;-) – ltjax
@KennyTM: Para encontrar el existente (nota: misma prioridad que el nuevo), primero encontramos la ubicación de inserción en el tiempo O (log N) , luego identifique la clave existente en esa ubicación (búsqueda binaria en O (log N)). ¿O qué me estoy perdiendo? – Frank