Montón de estructura de datos (cola de prioridad): montón bifurcado, montón d, montón izquierdo, montón sesgado y cola binomial

Este artículo es el quinto artículo de las notas de revisión de la estructura de datos. Se pueden encontrar otros artículos sobre el mismo tema en la siguiente URL: /nb/39256701

El montón también se llama. la cola de prioridad. Se basa en una cola y permite que se utilicen todos los elementos de la cola sin seguir necesariamente el mismo patrón que otros elementos de la cola.

En la parte superior de la cola (cola), el montón permite que todos los elementos de la cola no sigan necesariamente la regla de primero en entrar, primero en salir (FIFO), pero permite que cada elemento tenga un cierto prioridad, y el elemento con mayor prioridad será retirado de la cola primero.

Una cola de prioridad tiene al menos dos operaciones importantes:

Hay varias formas simples y obvias de implementar una cola de prioridad.

Un montón binario es una implementación de una cola de prioridad, simplemente podemos llamarlo montón

Un montón es un árbol binario completo, lo que significa que todos los nodos Debe haber un montón izquierdo niño y un niño derecho. Todos los nodos deben tener dos hijos izquierdo y derecho, excepto la última fila, que se rellena de izquierda a derecha hasta que no queden más elementos.

Claramente, un árbol binario completo de altura h tiene entre 2^h y 2^(h+1)-1 nodos, es decir, su altura se redondea hacia abajo a logN.

La ventaja de un árbol binario completo radica en su regularidad. Puede representarse mediante una matriz sin necesidad de una lista enlazada

Para cualquier elemento ubicado en la posición i-ésima. en la matriz, su hijo izquierdo en la posición 2i, su hijo derecho está una unidad (2i+1) después de su hijo izquierdo y su padre está en la posición i/2 redondeado hacia abajo.

Así que no sólo no se requiere cadena, sino que las operaciones requeridas para atravesar el árbol son muy simples y probablemente se ejecuten extremadamente rápido en la mayoría de las computadoras. El único problema es que el tamaño máximo del montón debe estimarse de antemano.

La propiedad que agiliza la operación es la propiedad de orden del montón: para cada nodo nodo.

Primero coloque el elemento a insertar en la última posición para asegurarse de que sea un árbol binario completo, luego compare el elemento con su nodo padre (i/2 redondea hacia abajo), si el elemento es menor que su nodo principal, los dos se intercambian y luego se comparan con el nuevo nodo principal. Este método se denomina penetración ascendente para obtener un montón superior pequeño (penetración ascendente).

Por ejemplo, para insertar el elemento 14 en el montón mínimo:

Buscar, devolver y eliminar el elemento más pequeño es muy simple: el elemento más pequeño es el elemento en el nodo raíz , y será devuelto y eliminado. El siguiente paso es lidiar con este B. Primero, tome el último elemento X. Si el elemento X es menor que los dos nodos secundarios de B, puede insertar X directamente en la posición de B si el más pequeño se inserta en B y B a su vez se mueve a este elemento secundario; nodo. Repita los pasos anteriores hasta que se pueda insertar X en B. Esta operación se llama filtrar hacia abajo

Por ejemplo, eliminar el nodo raíz de un pequeño montón superior

La operación disminuirKey(p, A) disminuye el valor del elemento en la posición p en A, Esto se interpreta como un aumento de la prioridad del elemento. Esta operación destruye la naturaleza del montón, por lo que se requiere una operación de filtrado ascendente para ajustar el montón.

incrementKey(p, A) La operación aumentarKey(p, A) aumenta el valor del elemento en la posición p en A, lo que puede entenderse como una reducción de la prioridad del elemento. Esta operación destruye las propiedades del montón, por lo que se requiere una operación de filtrado descendente para ajustar el montón.

La operación de eliminación (p) eliminará el nodo en la posición p en el montón. Esto se puede lograr ejecutando disminuirKey(p, ∞) y eliminarMin() consecutivamente, lo que puede interpretarse como una eliminación inmediata con. prioridad general. Los elementos de

Al realizar N operaciones de inserción continuamente, el conjunto primitivo se puede construir como un montón binario

Teorema: hay 2^(h+1)-1. nodos y una altura de El árbol binario perfecto de h tiene una altura 2^(h+1)-1-(h+1)

Un d-heap es una colección de d-heaps. (d-heap) es una generalización simple de un montón binario, que es muy similar a un montón binario, pero cada nodo tiene d nodos secundarios, por lo que un montón binario es un d-montón, con d igual a 2. Un montón d es un árbol completamente d-ario. Por ejemplo, un montón de 3 se ve así.

El montón d es mucho menos profundo que el montón binario y su tiempo de ejecución de inserción se reduce a O (logdN). Sin embargo, la operación eliminarMin lleva más tiempo porque requiere comparaciones d-1 para encontrar el más pequeño de los submontones d. El montón d no puede realizar operaciones de búsqueda y es difícil fusionar dos montones en uno. Esta operación adicional es la fusión.

¡Atención! (cola binomial) admite operaciones de fusión, inserción y eliminación mínima. El tiempo de ejecución en el peor de los casos de cada operación es O (logN), y el tiempo promedio de las operaciones de inserción permanece sin cambios.

La cola binaria no es un árbol ordenado en montón, sino una colección de árboles ordenados en montón, que se convierte en un bosque. Cada árbol ordenado en montón es un árbol binario acotado. Un árbol binario es un árbol con como máximo un árbol binario por altura. Un árbol binario con altura 0 es un árbol de un solo nodo, y un árbol binario Bk con altura k se forma conectando un árbol binario Bk-1 a la raíz de otro árbol binario Bk-1. A continuación se muestran los árboles binarios B0, B1, B2, B3 y B4.

Se puede observar que el árbol binario Bk consta de una raíz y los hijos B0, B1,... y Bk-1. Un árbol binario con altura k tiene exactamente 2^k nodos, y el número de nodos con profundidad d es el coeficiente binario Cdk.

Podemos representar de forma única una cola de prioridad de cualquier tamaño utilizando una colección de árboles binarios. Tomando una cola con un tamaño de 13 como ejemplo, la representación binaria de 13 es 1101, por lo que podemos usar los bosques binarios B3, B2 y B0 para representarlo. Es decir, cuando aparece un árbol Bk, el k-ésimo bit. La representación binaria del número es 1 y no aparece ningún árbol Bk. Cuando, el k-ésimo bit es 0. Por ejemplo, los montones H1 y H2 anteriores se pueden representar como las siguientes dos colas binarias:

La operación de fusión de colas binarias es muy simple; tome las colas binarias H1 y H2 anteriores como ejemplo.

En primer lugar, hay un B0 en H2 pero no en H1, por lo que el B0 en H2 se puede usar directamente como el árbol B0 de la nueva cola.

En segundo lugar, los dos en H1 y H2, B1 se puede fusionar en un nuevo árbol B2 colgando el montón con el nodo raíz más pequeño en el nodo raíz del montón con el nodo raíz más grande. Esto deja tres árboles B2. De esta manera, hay tres montones B2. El montón más grande del nodo raíz se colocará directamente en la nueva cola y se convertirá en su montón B2.

Finalmente, combine los dos montones B2 en el montón B3 en la nueva cola.

La operación eliminarMin de una cola binaria es muy simple. Solo necesita comparar los nodos raíz de todos los montones binarios en la cola, devolver y eliminar el valor mínimo, la complejidad del tiempo es O (logN). y luego realice la operación de fusión. También puede usar un espacio separado para registrar el valor mínimo cada vez, de modo que pueda devolverse en tiempo O (1).

Los árboles en el bosque se implementan usando la notación "hijo izquierdo, hermano derecho", y luego la cola binaria puede usar una matriz para registrar el nodo raíz de cada árbol en el bosque.

Por ejemplo, la cola binaria sintetizada anteriormente se puede representar de la siguiente manera:

En STL, el montón binario se implementa a través de la clase de plantilla Priority_queue y en la cola de archivos de encabezado, STL. implements Es un montón superior grande en lugar de un montón superior pequeño, y sus funciones miembro clave son las siguientes: