¿Existe una cola prioritaria con extractos de

46

Hay muchas estructuras de datos que implementan la interfaz de cola de prioridad:

  • Insertar: inserta un elemento en la estructura
  • Get-Min: devuelve el elemento más pequeño en la estructura
  • Extract-Min: elimina el elemento más pequeño de la estructura

Las estructuras de datos comunes que implementan esta interfaz son montones (min) .

Por lo general, los tiempos de ejecución (amortizados) de estas operaciones son:

  • Insertar: (a veces )O ( log n )O(1)O(logn)
  • Get-Min:O(1)
  • Extraer-Min:O(logn)

El montón de Fibonacci logra estos tiempos de ejecución, por ejemplo. Ahora, mi pregunta es la siguiente:

¿Existe una estructura de datos con los siguientes tiempos de ejecución (amortizados)?

  • Insertar:O(logn)
  • Get-Min:O(1)
  • Extraer-Min:O(1)

Si podemos construir dicha estructura en tiempo dado una entrada ordenada, entonces podemos encontrar intersecciones de línea en entradas pre-ordenadas con intersecciones estrictamente más rápidas que si utilizamos las colas de prioridad 'habituales'.o ( nO(n)o(nlogn)

Alex ten Brink
fuente
Creo que usar un BST equilibrado, eso no reequilibraría cuando hacer Extract-Min podría funcionar. O tal vez una lista de omisión.
svick
@svick: las listas de omisión son aleatorias, que no es lo que estoy buscando. Si puede hacerlo con un BST, entonces eso es genial, pero creo que tendrá que hacer algún tipo de equilibrio.
Alex ten Brink
En una nota al margen: esta es una pregunta inicial y sé la respuesta, pero es bueno ver que no se resuelve tan fácilmente. Si alguien sabe la respuesta, no dude en darla :)
Alex ten Brink
Si acepta tiempos de actualización amortizados, puede mantener sus estructuras de almacenamiento dinámico estándar y solo realizar modificaciones menores en su análisis. Vea mi respuesta a continuación.
Joe

Respuestas:

27

Nuestra idea es utilizar árboles de separación roscados . Aparte del artículo de Wikipedia, enhebraremos los árboles para que cada nodo tenga un puntero a su sucesor en el recorrido en orden; También mantenemos un puntero al elemento más pequeño del árbol.nextstart

Es fácil ver que es posible extraer el elemento más pequeño en el (peor de los casos) tiempo : simplemente siga el puntero, elimine el mínimo y cambie el puntero al mínimo . El mínimo nunca puede tener un hijo izquierdo; si tiene un hijo correcto, lo colocamos en el lugar mínimo en el árbol. Nosotros no realizamos los árboles ensanchamiento operación splay normalmente lo haría. El resultado es un árbol de búsqueda que todavía está razonablemente equilibrado: como solo eliminamos nodos en el flanco izquierdo, sabemos que cuando el número de nodos (en un subárbol afectado) cae a aproximadamente la mitad del número original debido a eliminaciones, el (sub ) la altura del árbol se reduce en uno.O(1)startnext

Las inserciones son posibles en tiempo amortizado; las operaciones en zig-zag (y lo que no) aquí también reequilibrarán muy bien el árbol.O(logn)

Este es un bosquejo aproximado en el mejor de los casos. Los créditos van para F. Weinberg, quien se quedó perplejo sobre la pregunta conmigo y nuestro asesor M. Nebel, quien mencionó los árboles de separación, sobre la única variante de árbol que no habíamos probado.

Rafael
fuente
2
No me queda claro cómo hacer que el análisis amortizado funcione si no juegas en extractMin. ¿Puedes dar una pista?
jbapple
No lo hemos hecho en detalle. La idea es que una serie de operaciones extract-min no desequilibre el árbol, por lo tanto, no es necesaria la reproducción y el análisis normal debería funcionar para las inserciones.
Raphael
99
¡Cuidado! Los árboles de separación no están necesariamente equilibrados. Los nodos a los que no se ha accedido en mucho tiempo pueden ser muy profundos en el árbol. Para hacer el análisis de ir a través, usted tiene que discutir en términos de la misma función potencial utilizado para analizar ensancha.
JeffE
20
  • Insertar:O(logn)
  • Get-Min:O(1)
  • Extraer-Min:O(1)

Tiempo amortizado

Las implementaciones simples de una cola prioritaria (por ejemplo, cualquier BST balanceada, o el binario min-montón estándar) pueden lograr estos tiempos de ejecución (amortizados) simplemente cargando el costo de Extraer-Min para insertar, y manteniendo un puntero al elemento mínimo. Por ejemplo, podría tener una función potencial que es . Luego, insertar un nuevo elemento aumenta el potencial en O ( log n ) , por lo que el costo amortizado del inserto sigue siendo O ( log n ) , pero Extract-Min () disminuye el potencial en Ω ( log n ) , por lo que el costo amortizado es solo O (cnlognO(logn)O(logn)Ω(logn) .O(1)

Peor de los casos

Puede usar una estructura de datos existente en la literatura: árboles de búsqueda de dedos y simplemente mantener un puntero al elemento mínimo. Consulte esta encuesta para obtener una descripción general y el documento de 1988 de Levcopoulos y Overmars para obtener una versión implementable que satisfaga sus necesidades.

Joe
fuente
1
Que astuto. Tienes razón, supongo que debería haber exigido algo más fuerte para excluir esto. Buena idea :)
Alex ten Brink
O(1)
14

O(1)O(1)

O(1)

O(1)

jbapple
fuente
8

A pedido, aquí está la estructura que encontré después de formular la pregunta:

La idea básica es usar un árbol de chivo expiatorio roscado junto con un puntero al mínimo (y, en buena medida, al máximo también). Una alternativa más simple al subprocesamiento es mantener punteros predecesores y sucesores en cada nodo (que es equivalente, más simple, pero tiene más sobrecarga). He venido a llamarlo un montón de chivo expiatorio , solo para darle un nombre.

Solo esta estructura básica le ofrece estas operaciones:

  • O(logn)
  • O(logn)
  • O(1)
  • Get-Min / Max: devuelve el puntero al mínimo o al máximo.

O(logn)O(1)O(logn)O(1)O(1)O(1)

  • O(1)

Combinando esto:

  • O(1)

Puede hacer un poco más con los punteros: por ejemplo, no es difícil mantener un puntero a la mediana o alguna otra estadística de orden, por lo que puede mantener un número constante de dichos punteros si los necesita.

Algunas otras cosas:

  • nO(n)
  • O(n)

Y finalmente, estoy bastante seguro de que puede admitir estas operaciones, pero necesito pensar un poco más antes de saber esto con seguridad:

  • O(1)
Alex ten Brink
fuente
La idea clave es que los árboles de chivo expiatorio le aseguran que eliminar cualquier nodo sin reequilibrar no afecta el rendimiento de otras operaciones a largo plazo, incluso si elimina muchos nodos.
Raphael
O(lgn)O(1)O(lgn)
2
O(1)O(1)O(1)O(1)
Alex ten Brink
Ah, ahora entiendo.
jbapple
2

ϵO(1)log(1/ϵ)ϵ

ϵn

Para el artículo original, claro y bien escrito, vea Bernard Chazelle, The Soft Heap: An Approximate Priority Queue with Optimal Error Rate, Journal of the ACM, 47 (6), pp. 1012-1027, 2000 . Para una implementación y análisis alternativos que afirman ser más simples e intuitivos de SODA'09, vea Kaplan H. & Zwick U., Una implementación y análisis más simple de los montones suaves de Chazelle, 2009 .

Juho
fuente
Aunque es una estructura de datos muy interesante, los montones suaves no son exactos: findmin puede devolver un valor que no es el mínimo, sino que es simplemente un mínimo aproximado. Gracias por los enlaces de todos modos :)
Alex ten Brink
1
@AlextenBrink: el objetivo de la estructura de datos (como muchos algoritmos probabilísticos) es que puede usar una estructura de datos aproximada para obtener respuestas exactas. De hecho, la naturaleza aproximada de los montones suaves no impidió que se usara en el único algoritmo de tiempo lineal conocido para un árbol de expansión mínima.
Jérémie
2

Bien, finalmente conseguí la complejidad que estabas buscando, y lo que es mejor, lo encontré en la literatura:

La peor complejidad del caso

O(1)

O(1)

O(1)

O(log n)

Referencia

[3]O(1)O(log n)O(n)

Brodal, Gerth Stølting. 'Colas de prioridad fusionables rápidas'. En Actas del 4º Taller internacional sobre algoritmos y estructuras de datos, 282–290. WADS '95. Londres, Reino Unido, Reino Unido: Springer-Verlag, 1995.

[3]: Dietz, Paul F y Rajeev Raman. 'Un árbol de búsqueda de dedo de tiempo de actualización constante'. Cartas de procesamiento de información 52, no. 3 (1994): 147-154.

Aunque esto utiliza el modelo de cálculo RAM :

Nuestra estructura de datos utiliza el modelo de máquina de acceso aleatorio (RAM) con medida de costo unitario y tamaño de palabra logarítmico;

Más recientemente, se ha proporcionado un modelo de solución de cálculo Pointer-Machine[1] .

[1]: Brodal, Gerth Stølting, George Lagogiannis, Christos Makris, Athanasios Tsakalidis y Kostas Tsichlas. 'Árboles óptimos de búsqueda de dedos en la máquina de puntero'. J. Comput. Syst. Sci. 67, no. 2 (septiembre de 2003): 381–418.

A
fuente
2

Abordar este problema manteniendo dos estructuras de datos: una matriz y un árbol binario.

Ω(lognloglogn)Ω(logn)

O(logn)O(logn)

nullO(logn)

O(1)O(1)

O(logn)O(1)delete_at(idx)


1 Patrascu, Mihai y Erik D. Demaine. "Límites inferiores logarítmicos en el modelo de sonda celular". SIAM J. Comput. 35, no. 4 (abril de 2006): 932–963. doi: 10.1137 / S0097539705447256.

A
fuente
1
O(logn)
¿Qué significa "enhebrar un árbol de búsqueda binario en una matriz"?
jbapple
@AT: comparto el sentimiento de jbapple.
Raphael
Ω(k)kO(1)
Su actualización, en la que explica cómo implementar rotaciones en tiempo constante, no funciona en matrices. Esta respuesta sigue siendo incorrecta. El documento de Tarjan al que hace referencia trata sobre árboles almacenados con nodos y punteros.
jbapple
-2

O(1)O(log log n)

Vea el documento de 2007: Equivalencia entre colas prioritarias y clasificación por Mikkel Thorup.

O(n log log n)

A
fuente
Aunque el documento que vinculó es interesante, la cola de prioridad que presentan no tiene eliminaciones de tiempo constantes (si leo el resumen correctamente) y, por lo tanto, no es lo que estoy pidiendo.
Alex ten Brink
-2

Análisis

o(n log log n)

o(log log n)

O(1)

O(n)

O(1)

O(1)

Implementación

  1. O(1)
  2. O(6)O(1)
  3. k±
    ((k>nsize1)(k<n0)((k<ni)(k>ni+1)))
    o(log log n)

[1]: Andersson, Arne y Christer Mattsson. 'Búsqueda de interpolación dinámica en O (log log n) Time'. En Automata, Languages ​​and Programming, editado por Andrzej Lingas, Rolf Karlsson y Svante Carlsson, 700: 15–27. Lecture Notes in Computer Science. Springer Berlin / Heidelberg, 1993. http://dx.doi.org/10.1007/3-540-56939-1_58 .

A
fuente
2
Bueno, el tiempo de inserción está muy lejos de la marca.
Raphael
nsize1n0nini+1
Al leer el resumen del documento que vincula, parece que estos límites son límites esperados para las entradas de una distribución en particular, por lo que no es lo que estoy buscando: quiero los límites que menciono en cualquier entrada.
Alex ten Brink
O(log n)
@AT La búsqueda binaria logarítmica necesita acceso aleatorio. ¿Cómo se implementa la lista subyacente? Realmente deberías discutir por tus límites reclamados. Además, "posiciones en la lista" es vago: ¿a qué posiciones y a qué se refieren los símbolos? No todos tienen acceso al papel que vinculó. Intente que su respuesta (más) sea autónoma y al menos resuma los hechos. En este punto, no creo que su respuesta sea correcta.
Juho