En muchas discusiones sobre el almacenamiento dinámico binario, normalmente solo la tecla de disminución aparece como operación admitida para un almacenamiento dinámico mínimo. Por ejemplo, CLR capítulo 6.1 y esta página de wikipedia . ¿Por qué la clave de aumento normalmente no aparece en min-heap? Me imagino que es posible hacer eso en O (altura) intercambiando iterativamente el elemento aumentado (x) con el mínimo de sus hijos, hasta que ninguno de sus hijos sea mayor que x.
p.ej
IncreaseKey(int pos, int newValue)
{
heap[pos] = newValue;
while(left(pos) < heap.Length)
{
int smallest = left(pos);
if(heap[right(pos)] < heap[left(pos)])
smallest = right(pos);
if(heap[pos] < heap[smallest])
{
swap(smallest, pos);
pos= smallest;
}
else return;
}
}
¿Es correcto lo anterior? Si no, ¿por qué? En caso afirmativo, ¿por qué no aparece la clave de aumento para min-heap?
algorithms
data-structures
heaps
priority-queues
GatotPujo
fuente
fuente
Respuestas:
El algoritmo que sugiere es simplemente heapify. Y, de hecho, si aumenta el valor de un elemento en un montón mínimo y luego heapifica su subárbol, terminará con un montón mínimo legal.
fuente
La razón por la que su operación no figura en la lista, es que uno no está simplemente interesado en todas las operaciones que pueden implementarse fácilmente utilizando una determinada estructura de datos, sino más bien de otra manera. Dado un conjunto de operaciones, cuál es la forma más eficiente (en términos de espacio y tiempo) para implementar estas operaciones. (Pero agrego más a esto más adelante)
Los montones binarios implementan la cola de prioridad de estructura de datos abstractos, que solicita operaciones is_empty, add_element (una clave con su prioridad), find_min y delete_min. Las colas más avanzadas también permiten disminuir la prioridad de la clave (en un min_heap) o incluso aumentarla. De hecho, ha dado una implementación.
Dos observaciones Su operación se utiliza en la función heapify, que construye eficientemente un montón a partir de una matriz. En heapify, su operación se repite (a partir de la última tecla).
Luego, lo más importante, su código usa la posición del nodo. Para la cola de prioridad de estructura de datos pura que es trampa. Esa estructura de datos pide realizar una determinada operación dada una clave. Entonces, para disminuir o aumentar la prioridad de un elemento, primero tendrá que localizarlo. Creo que esa es la razón principal por la que no está en la lista.
fuente
Creo que lo primero a considerar es ¿qué es una operación compatible?
¿"Insertar un valor con una clave fija específica" (por ejemplo, para claves tomadas del reino entero, insertar con clave = 3) corresponde a una operación admitida para el montón mínimo?
No, porque esa operación se puede implementar de manera trivial con operaciones más generales compatibles. Del mismo modo, la inserción de 2 elementos a la vez se puede hacer con la
insertoperación existente .Por otro lado, la
insertoperación no se puede definir de otra manera que exponiendo los detalles de implementación. Es prácticamente lo mismo para las operaciones enumeradas en la página de wikipedia,heapifyexcepto que probablemente podrían implementarse mediante una secuencia deinsert.En otras palabras, hay operaciones elementales proporcionadas en el tipo, que están estrechamente vinculadas a los detalles de implementación para que funcionen bien, y hay otras operaciones que no cumplen con esa regla y, por lo tanto, pueden implementarse como combinaciones de los canónicos.
Con esa definición en mente, ¿cree que la tecla de aumento podría implementarse con otras operaciones compatibles de forma exclusiva, sin pérdida de rendimiento? Si es así, entonces no es una operación compatible con la definición anterior, de lo contrario, es posible que tenga razón.
Podría decirse que la definición de una operación compatible que proporciono es mía, que yo sepa. No es formal y, por lo tanto, está sujeto a discusión (aunque me parece bastante claro). Sin embargo, me alegraría si alguien pudiera proporcionar una fuente que defina clara e inequívocamente qué es una operación compatible para los tipos de datos, o al menos la defina en mejores términos que la mía (¿esa definición se da en CLR? No tengo una copia )
Mi segundo punto será sobre cómo definimos una cola prioritaria (que es la razón de ser de los montones binarios). ¿Es la
increase_keyoperación necesaria para ese tipo de datos, es decir, para su uso adecuado?Como puede ver, mi ángulo tiene que ver con las definiciones. Realmente no proporciono una respuesta a sus preguntas, solo algunos consejos, por lo que las mejoras son bienvenidas.
fuente