Cola de prioridad con una función de búsqueda - Implementación más rápida

Question

Estoy buscando implementar una cola de prioridad con un requisito adicional, una función de búsqueda/búsqueda que dirá si un elemento está en algún lugar dentro de la cola. Entonces las funciones serán: insert, del-min y find.

No estoy seguro de si debería usar un árbol de búsqueda binaria Heap o uno autoequilibrante. Parece que los PQ generalmente se implementan con un Heap, pero me pregunto si hay alguna ventaja al usar un árbol de búsqueda binario ya que también necesito esa función de búsqueda.

Además, en promedio haré más insertos que borrados. También estoy considerando un d-ary heap. Básicamente, cada segundo cuenta.

Gracias!

Answer 1

IIRC buscar/buscar en un montón es O(n) mientras que en un árbol es O(log(n)) y las otras operaciones de PQ estándar son las mismas.

Los montones son solo empíricamente más eficientes por algún factor constante, por lo que si es una gran cola, un árbol debería ser mejor, si es pequeño, debe probarlo y perfilarlo. es bueno saber en teoría qué es más rápido, pero si esos factores constantes son grandes, puede ser completamente irrelevante para conjuntos de datos suficientemente pequeños.

Answer 2

¿Por qué no puedes simplemente usar una cola de prioridad y un conjunto? Cuando encola algo, lo agrega al conjunto. Cuando lo quita, lo quita del conjunto. De esa forma, el conjunto te dirá si hay algo en la cola.

Answer 3

Si su operación de búsqueda es relativamente infrecuente (y su montón bastante pequeño), simplemente haría una búsqueda lineal. Si es relativamente frecuente, o el montón es enorme, considere rastrear la membresía de heap (para hacer su prueba de "búsqueda") con una estructura de datos separada o una bandera de objeto. La alegría de la indexación externa es poder colocar su objeto en tantos contenedores como desee.

Si con 'Buscar' quiere decir 'buscar y modificar' (me parece que a menudo necesito eliminar cosas de las colas de prioridad independientemente de la típica inserción/del-min), aquí hay tres enfoques que he usado:

Dada una alta tasa de inserción/del-min (100k/s continuo) y una baja tasa de búsqueda-eliminación (digamos 1/s) en un conjunto de trabajo bastante pequeño (500-1000) Hice una búsqueda lineal para el elemento y luego lo eliminó del árbol de la manera estándar.

Teniendo en cuenta una alta tasa de inserción/del-min más bastante frecuentes de búsqueda y eliminación, simplemente marqué los objetos eliminados como "poco interesantes" después de encontrarlos indirectamente. La real libre se difirió hasta que el objeto fue quitado de la cola como de costumbre.

Dado un pequeño std :: priority_queue (que no tiene métodos de acceso fuera de insert/del-min) de solo algunos elementos y eliminaciones bastante infrecuentes, acabo de copiar toda la cola a un std :: vector temporal y copié la parte modificada/deseada vuelve a la cola. Entonces lloré para dormir.

Answer 4

Almacene sus datos en el contenedor más rápido que haya probado y use un filtro bloom para comprobar si hay algo en el contenedor.

Conecté un filtro de floración con una tabla hash en un proyecto anterior y aceleró las cosas hasta 400 veces en tablas hash con un promedio de aproximadamente 10k elementos.

El filtro de floración tiene algunas propiedades interesantes:

• Si la respuesta es no, de un filtro de floración, que es 100% fiable.
• Si la respuesta es sí, debe verificar la estructura de los otros datos para asegurarse de que el elemento está realmente presente.
• Asegúrese de elegir una buena función hash :)

Answer 5

Si necesita los beneficios de más de una estructura de datos entonces se puede utilizar en la composición . Por ejemplo, si necesita los beneficios de una cola de prioridad y un árbol de búsqueda binario, realice las acciones que desee en ambos.

Si es insert, inserte el elemento en ambas.

Si es find entonces puede encontrar el elemento utilizando el árbol de búsqueda binaria y, si lo encontró, continúe para encontrarlo en la cola de prioridad.

Si es min, quítelo primero de la cola de prioridad y ahora que sabe qué elemento es, puede eliminarlo del árbol de búsqueda binaria.

si es del, primero búscalo en el árbol de búsqueda binaria y quítalo, continúa encontrándolo en la cola de prioridad y quítalo también de allí.

Se supone que los nodos del árbol binario y los nodos de la cola de prioridad son punteros a sus elementos.

Answer 6

Radix trees con una propiedad min-heap proporcionará las propiedades que necesita. Esto realmente le dará complejidades de tiempo constante para sus operaciones. Por ejemplo, si miramos this Haskell implementation, las tres operaciones que menciona tienen complejidad de tiempo O (min (n, W)). Donde n es el número de elementos, y W es el número de bits en un int (32 o 64).