¿Hay un montón estable?

32

¿Existe una estructura de datos de cola prioritaria que admita las siguientes operaciones?

  • Insertar (x, p) : agrega un nuevo registro x con prioridad p
  • StableExtractMin () : devuelve y elimina el registro con prioridad mínima, rompiendo los lazos por orden de inserción .

Por lo tanto, después de Insertar (a, 1), Insertar (b, 2), Insertar (c, 1), Insertar (d, 2), una secuencia de StableExtractMin's devolvería a, luego c, luego b, luego d.

Obviamente, uno podría usar cualquier estructura de datos de cola prioritaria almacenando el par como la prioridad real, pero estoy interesado en estructuras de datos que no almacenen explícitamente los tiempos de inserción (u orden de inserción), por analogía con la ordenación estable .(p,time)

Equivalentemente (?): ¿Existe una versión estable de heapsort que no requiera espacio adicional ?Ω(n)

Jeffε
fuente
Creo que quiere decir "a, luego c, luego b, luego d"?
Ross Snider
¿No funcionará el montón con la lista vinculada de registros + árbol binario equilibrado marcado con prioridad que apunta a la lista vinculada correspondiente? ¿Qué me estoy perdiendo?
Aryabhata
Moron: Eso es almacenar el orden de inserción explícitamente, que es precisamente lo que quiero evitar. Aclaré el enunciado del problema (y arreglé el error tipográfico de Ross).
Jeff el

Respuestas:

16

El método Bently-Saxe proporciona una cola de prioridad estable bastante natural.

Almacene sus datos en una secuencia de matrices ordenadas . tiene el tamaño . Cada matriz también mantiene un contador . Las entradas de matriz contienen datos.A0,,AkAi2iciAi[ci],,Ai[2i1]

Para cada , todos los elementos en se agregaron más recientemente que los de y dentro de cada elementos se ordenan por valor, y los lazos se rompen colocando los elementos más antiguos delante de los más nuevos. Tenga en cuenta que esto significa que podemos fusionar y y preservar este orden. (En el caso de empates durante la fusión, tome el elemento de ).A i A i + 1 A i A i A i + 1 A i + 1iAiAi+1AiAiAi+1Ai+1

Para insertar un valor , encontrar la más pequeña tal que contiene 0 elementos, fusión y , almacenar esto en y conjunto adecuadamente.i A i A 0 , , A i - 1 x A ixiAiA0,,Ai1xAic0,,ci

Para extraer el mínimo, encuentre el índice más grande tal que el primer elemento en sea ​​mínimo sobre todo e incremente .A i [ c iii c iAi[ci]ici

Según el argumento estándar, esto le da a tiempo amortizado por operación y es estable debido al orden descrito anteriormente.O(logn)

Para una secuencia de inserciones y extracciones, esto usa entradas de matriz (no mantenga matrices vacías) más palabras de datos de contabilidad. No responde la versión de Mihai de la pregunta, pero muestra que la restricción estable no requiere una gran cantidad de espacio. En particular, muestra que no hay un límite inferior en el espacio extra necesario.n O ( log nnnΩ ( n )O(logn)Ω(n)

Actualización: Rolf Fagerberg señala que si podemos almacenar valores nulos (sin datos), toda esta estructura de datos se puede empaquetar en una matriz de tamaño , donde es el número de inserciones hasta ahora.nnn

Primero, observe que podemos empaquetar en una matriz en ese orden (con primero, seguido de si no está vacío, y así sucesivamente). La estructura de esto está completamente codificada por la representación binaria de , el número de elementos insertados hasta ahora. Si la representación binaria de tiene un 1 en la posición , entonces ocupará la ubicación de la matriz , de lo contrario no ocupará ninguna ubicación de la matriz.A k A k - 1 n n iAk,,A0AkAk1nni2 iAi2i

Al insertar, , y la longitud de nuestra matriz, aumentan en 1, y podemos fusionar más el nuevo elemento usando algoritmos de fusión estables existentes.AnA0,,Ai

Ahora, donde usamos valores nulos es en deshacernos de los contadores . En , almacenamos el primer valor, seguido de los valores nulos de , seguidos de los valores restantes . Durante un extract-min, todavía podemos encontrar el valor para extraer en tiempo examinando . Cuando encontramos este valor en establecemos en nulo y luego hacemos una búsqueda binaria en para encontrar el primer valor no nulo e intercambiamos y .A i c i 2 i - c i - 1 O ( log n ) A 0 [ 0 ] , , A k [ 0 ] A i [ 0 ] A i [ 0 ] A i A i [ c i ] A i [ 0 ] A i [ c i ]ciAici2ici1O(logn)A0[0],,Ak[0]Ai[0]Ai[0]AiAi[ci]Ai[0]Ai[ci]

El resultado final: toda la estructura se puede implementar con una matriz cuya longitud se incrementa con cada inserción y un contador, , que cuenta el número de inserciones.n

Pat Morin
fuente
1
Esto utiliza potencialmente espacio adicional de O (n) en un instante dado después de las extracciones de O (n), ¿no? En este punto, también podrías almacenar la prioridad ...
Mehrdad
10

No estoy seguro de cuáles son sus limitaciones; ¿califica lo siguiente? Almacene los datos en una matriz, que interpretamos como un árbol binario implícito (como un montón binario), pero con los elementos de datos en el nivel inferior del árbol en lugar de en sus nodos internos. Cada nodo interno del árbol almacena el menor de los valores copiados de sus dos hijos; en caso de empate, copie al niño izquierdo.

Para encontrar el mínimo, mira la raíz del árbol.

Para eliminar un elemento, márquelo como eliminado (eliminación diferida) y propague el árbol (cada nodo en la ruta a la raíz que contenía una copia del elemento eliminado debe reemplazarse con una copia de su otro elemento secundario). Mantenga un recuento de elementos eliminados y, si alguna vez llega a ser una fracción demasiado grande de todos los elementos, reconstruya la estructura conservando el orden de los elementos en el nivel inferior: la reconstrucción toma tiempo lineal, por lo que esta parte solo agrega tiempo amortizado constante complejidad de la operación

Para insertar un elemento, agréguelo a la siguiente posición libre en la fila inferior del árbol y actualice la ruta a la raíz. O, si la fila inferior se llena, duplique el tamaño del árbol (nuevamente con un argumento de amortización; tenga en cuenta que esta parte no es diferente de la necesidad de reconstruir cuando un montón binario estándar supera su matriz).

Sin embargo, no es una respuesta a la versión más estricta de la pregunta de Mihai, porque usa el doble de memoria que una verdadera estructura de datos implícita, incluso si ignoramos el costo espacial de manejar las eliminaciones de manera perezosa.

David Eppstein
fuente
Me gusta esto. Al igual que con un montón mínimo de árbol implícito regular, probablemente el árbol implícito de 3 o 4 arios será más rápido debido a los efectos de caché (aunque necesita más comparaciones).
Jonathan Graehl
8

¿Es la siguiente una interpretación válida de su problema:

Debe almacenar N claves en una matriz de A [1..N] sin información auxiliar, de modo que pueda admitir: * insert key * delete min, que selecciona el primer elemento insertado si hay múltiples mínimos

Esto parece bastante difícil, dado que la mayoría de las estructuras de datos implícitas juegan el truco de codificar bits en el orden local de algunos elementos. Aquí, si varios tipos son iguales, se debe preservar su orden, por lo que no son posibles tales trucos.

Interesante.

Mihai
fuente
1
Creo que esto debería ser un comentario, no una respuesta, ya que en realidad no responde la pregunta original. (Puede eliminarlo y agregarlo como comentario.)
Jukka Suomela
55
Sí, este sitio web es un poco ridículo. Tenemos reputaciones, bonificaciones, recompensas, todo tipo de formas de comentar que no puedo entender. Desearía que esto se pareciera menos a un juego de niños.
Mihai
1
Creo que necesita más representante para publicar un comentario. ese es el problema.
Suresh Venkat
@Suresh: Oh, claro, no lo recordaba. ¿Cómo se supone que debemos manejar este tipo de situación (es decir, un nuevo usuario necesita pedir aclaraciones antes de responder una pregunta)?
Jukka Suomela
2
sin sálida fácil. He visto esto a menudo en MO. Mihai no tendrá problemas para ganar reputación, si es el Mihai, creo que es :)
Suresh Venkat
4

Respuesta corta: no puedes.

Respuesta un poco más larga:

Necesitará espacio adicional para almacenar la "edad" de su entrada que le permitirá discriminar entre prioridades idénticas. Y necesitará espacio para información que permita inserciones y recuperaciones rápidas. Además de su carga útil (valor y prioridad).Ω ( n )Ω(n)Ω(n)

Y, por cada carga útil que almacene, podrá "ocultar" cierta información en la dirección (por ejemplo, significa que Y es anterior a X). Pero en esa información "oculta", ocultará la "edad", O la información de "recuperación rápida". No ambos.addr(X)<addr(Y)


Respuesta muy larga con pseudo-matemáticas inexactas:

Nota: el final de la segunda parte es incompleto, como se mencionó. Si algún matemático pudiera proporcionar una versión mejor, estaría agradecido.

Pensemos en la cantidad de datos involucrados en una máquina de X bits (digamos 32 o 64 bits), con registros (valor y prioridad) de palabras de máquina ancho.P

Tiene un conjunto de registros potenciales que está parcialmente ordenado: y pero no puede comparar y .( a , 1 ) = ( a , 1 ) ( a , 1 )(a,1)<(a,2)(a,1)=(a,1)(a,1)(b,1)

Sin embargo, desea poder comparar dos valores no comparables de su conjunto de registros, en función de cuándo se insertaron. Por lo que tiene aquí otro conjunto de valores: los que se han insertado, y quiere mejorarla con un orden parcial: si y sólo si se insertan antes de .X<YYXY

En el peor de los casos, su memoria se llenará con registros del formulario (con Diferente para cada uno), por lo que tendrá que confiar completamente en el tiempo de inserción para decidir cuál va fuera primero.?(?,1)?

  • El tiempo de inserción (en relación con otros registros aún en la estructura) requiere bits de información (con carga útil de byte P y bytes de memoria accesibles).Xlog2(P)2X
  • La carga útil (el valor y la prioridad de su registro) requiere palabras de información de la máquinaP

Eso significa que de alguna manera debe almacenar bits adicionales de información para cada registro que almacene. Y eso es para registros.O ( n )Xlog2(P)O(n)n

Ahora, ¿cuántos bits de información nos proporciona cada "célula" de memoria?

  • W bits de datos ( es el ancho de palabra de la máquina).W
  • X bits de dirección.

Ahora, supongamos (la carga útil tiene al menos una palabra de máquina de ancho (generalmente un octeto)). Esto significa que , por lo que podemos ajustar la información del orden de inserción en la dirección de la celda. Eso es lo que sucede en una pila: las celdas con la dirección más baja ingresaron primero a la pila (y saldrán al final).X - l o g 2 ( P ) < XP1Xlog2(P)<X

Entonces, para almacenar toda nuestra información, tenemos dos posibilidades:

  • Almacene el orden de inserción en la dirección y la carga útil en la memoria.
  • Almacene ambos en la memoria y deje la dirección libre para algún otro uso.

Obviamente, para evitar el desperdicio, usaremos la primera solución.


Ahora para las operaciones. Supongo que deseas tener:

  • Insert(task,priority) con complejidad de tiempo.O(logn)
  • StableExtractMin() con complejidad de tiempo.O(logn)

Veamos :StableExtractMin()

El algoritmo realmente muy general es así:

  1. Encuentre el registro con prioridad mínima y "tiempo de inserción" mínimo en .O(logn)
  2. Eliminarlo de la estructura en .O(logn)
  3. Devolverlo.

Por ejemplo, en el caso de un montón, se organizará de forma ligeramente diferente, pero el trabajo es el mismo: 1. Busque el registro mínimo en 2. Elimínelo de la estructura en 3. Arregle todo para que la próxima vez # 1 y # 2 sigan siendo es decir, "repare el montón". Esto debe hacerse en "O (log n)" 4. Devuelva el elemento.0(1)O(1)O(1)

Volviendo al algoritmo general, vemos que para encontrar el registro en el tiempo , necesitamos una forma rápida de elegir el correcto entre candidatos (en el peor de los casos, la memoria es lleno).O(logn)2(Xlog2(P))

Esto significa que necesitamos almacenar bits de información para recuperar ese elemento (cada bit divide el espacio candidato, por lo que tenemos bisecciones , lo que significa complejidad de tiempo).Xlog2(P)O(logn)O(logn)

Estos bits de información pueden almacenarse como la dirección del elemento (en el montón, el mínimo está en una dirección fija) o, por ejemplo, con punteros (en un árbol de búsqueda binario (con punteros), debe seguir en promedio para llegar al mínimo).O(logn)

Ahora, al eliminar ese elemento, necesitaremos aumentar el siguiente registro mínimo para que tenga la cantidad correcta de información para permitir la recuperación de próxima vez, es decir, que tenga bits de información que lo discrimina de los otros candidatos.O(logn)Xlog2(P)

Es decir, si no tiene suficiente información, deberá agregar algo. En un árbol de búsqueda binario (no equilibrado), la información ya está allí: tendrá que colocar un puntero NULO en algún lugar para eliminar el elemento, y sin ninguna otra operación, se puede buscar el BST en tiempo en promedio.O(logn)

Después de este punto, es un poco incompleto, no estoy seguro de cómo formular eso. Pero tengo la fuerte sensación de que cada uno de los elementos restantes en su conjunto necesitará tener bits de información que ayudarán a encontrar el próximo minuto y aumentarlo con suficiente información para que pueda encontrarse en hora la próxima vez.O ( l o g n )Xlog2(P)O(logn)

El algoritmo de inserción generalmente solo necesita actualizar parte de esta información, no creo que cueste más (en cuanto a memoria) hacer que funcione rápidamente.


Ahora, eso significa que necesitaremos almacenar más bits de información para cada elemento. Entonces, para cada elemento, tenemos:Xlog2(P)

  • El tiempo de inserción, bits.Xlog2(P)
  • Las palabras de la máquina carga útil .P
  • La información de "búsqueda rápida", bits.Xlog2(P)

Como ya usamos el contenido de la memoria para almacenar la carga útil y la dirección para almacenar el tiempo de inserción, no nos queda espacio para almacenar la información de "búsqueda rápida". Así que tendremos que asignar algo de espacio extra para cada elemento, y así "desperdiciar" espacio extra.Ω(n)

Suzanne Dupéron
fuente
¿Realmente tenía la intención de dar su respuesta CW?
Suresh Venkat
Sí. Mi respuesta no es 100% correcta, como se indica en el interior, y sería bueno si alguien pudiera corregirlo incluso si ya no estoy en SO o lo que sea. El conocimiento debe ser compartido, el conocimiento debe ser cambiante. Pero tal vez no entendí bien el uso de CW, si es así, por favor dígame :). EDITAR: whoops, de hecho, acabo de descubrir que no obtendré ningún representante de las publicaciones de CW y que el contenido tiene licencia CC-wiki de ninguna manera ... Lástima :).
Suzanne Dupéron
3

Si implementa su cola de prioridad como un árbol binario equilibrado (una opción popular), entonces solo debe asegurarse de que cuando agrega un elemento al árbol, se inserta a la izquierda de cualquier elemento con igual prioridad.
De esta manera, el orden de inserción se codifica en la estructura del árbol mismo.

TonyK
fuente
1
Pero esto agrega espacio O (n) para los punteros, que creo que es lo que el interlocutor quiere evitar.
Jeremy
-1

No creo que sea posible

caso concreto:

       x
    x    x
  x  x  1  x
1  x  

montón mínimo con todo x> 1

heapifying eventualmente dará una opción a algo así

       x
    1    1
  x  x  x  x
x  x  

ahora cual 1 propagar a root?

monstruo de trinquete
fuente