Tutorial de estructura de datos de Heap

Los datos son un conjunto de valores. Los datos se pueden recopilar y colocar en una fila, o en una columna, o en una tabla o en forma de árbol. La estructura de los datos no es solo la colocación de datos en cualquiera de estos formularios. En la computación, la estructura de datos es cualquiera de estos formatos, más la relación entre los valores, más las operaciones (funciones) funcionan en los valores. Ya debería tener conocimientos básicos sobre la estructura de datos de los árboles antes de venir aquí, ya que los conceptos allí, se utilizarán aquí con poca o ninguna explicación. Si no tiene ese conocimiento, lea el tutorial titulado Tutorial de estructura de datos de Tree para principiantes, en el enlace, https: // Linuxhint.com/tree_data_structure_tutorial_beginners/. Después de eso, continúe leyendo este tutorial.Una estructura de datos del montón es un árbol binario completo o casi completo, donde el niño de cada nodo es igual o menor en valor que el valor de su padre. Alternativamente, es un árbol así donde el valor de un padre es igual o menor que el valor de cualquiera de sus hijos. El valor (dato) de un árbol también se llama clave.

Ilustración de estructuras de datos de montón

Hay dos tipos de montones: un máximo de tiempo y un mínimo-montón. Una estructura máxima de montón es donde el valor máximo es la raíz, y los valores se hacen más pequeños a medida que el árbol desciende; Cualquier padre es igual o mayor en valor que cualquiera de sus hijos inmediatos. Una estructura de mínimo-montón es donde el valor mínimo es la raíz, y los valores se hacen más grandes a medida que el árbol desciende; Cualquier padre es igual o menor en valor que cualquiera de sus hijos inmediatos. En los siguientes diagramas, el primero es un máximo y el segundo es un mínimo:

Para ambos montones, observe que para un par de niños, no importa si el de la izquierda es el valor mayor. Una fila en un nivel en el árbol, no debe llenarse necesariamente de mínimo a máximo, desde la izquierda; tampoco se llena necesariamente de máximo a mínimo, desde la izquierda.

Representar un montón en una matriz

Para que el software use un montón fácilmente, el montón debe representarse en una matriz. El máximo-helado de arriba, representado en una matriz es:

89, 85, 87, 84, 82, 79, 73, 80, 81 ,, 65, 69

Esto se hace comenzando con el valor raíz como el primer valor para la matriz. Los valores se colocan continuamente leyendo el árbol de izquierda a derecha, de arriba a abajo. Si un elemento está ausente, se omite su posición en la matriz. Cada nodo tiene dos hijos. Si un nodo está en el índice (posición) n, su primer hijo en la matriz está en el índice 2n+1, y su siguiente hijo está en el índice 2n+2. 89 está en el índice 0; Su primer hijo, 85 está en el índice 2 (0)+1 = 1 mientras que su segundo hijo está en el índice 2 (0)+2 = 2. 85 está en el índice 1; Su primer hijo, 84, está en el índice 2 (1)+1 = 3, mientras que su segundo hijo, 82 está en el índice 2 (1)+2 = 4. 79 está en el índice 5; Su primer hijo, 65 está en el índice 2 (5)+1 = 11 mientras que su segundo hijo está en el índice 2 (5)+2 = 12. Las fórmulas se aplican al resto de los elementos en la matriz.

Tal matriz, donde el significado de un elemento y la relación entre los elementos, está implícito en la posición del elemento, se denomina estructura de datos implícita.

La estructura de datos implícitas para el mínimo anterior es:

65, 68, 70, 73, 71, 83, 84 ,, 79, 80 ,, 85, 89

El máximo de máximo es un árbol binario completo pero no un árbol binario completo. Es por eso que algunas ubicaciones (posiciones) están vacías en la matriz. Para un árbol binario completo, ninguna ubicación estará vacía en la matriz.

Ahora, si el montón fuera un árbol casi completo, por ejemplo, si faltaba el valor 82, entonces la matriz sería:

89, 85, 87, 84, 79, 73, 80, 81 ,, 65, 69

En esta situación, tres ubicaciones están vacías. Sin embargo, las fórmulas aún son aplicables.

Operaciones

Una estructura de datos es un formato de datos (e.gramo. un árbol), más la relación entre los valores, más las operaciones (funciones) se realizan en los valores. Para un montón, la relación que corre a través de todo el montón es que el padre debe ser igual o mayor en valor que los niños, para un máximo de montón; y el padre debe ser igual o menos en valor que los niños, para un mínimo de tiempo. Esta relación se llama propiedad del montón. Las operaciones de un montón se agrupan bajo los títulos de creación, básicos, internos e inspección. Sigue un resumen de las operaciones del montón:

Resumen de operaciones de montón

Hay ciertas operaciones de software que son comunes con los montones, de la siguiente manera:

Creación de un montón

create_heap: crear un montón significa formar un objeto que represente el montón. En el idioma C, puede crear un montón con el tipo de objeto struct. Uno de los miembros de la estructura será la matriz de montón. El resto de los miembros serán funciones (operaciones) para el montón. Create_heap significa crear un montón vacío.

Heapify: la matriz de montón es una matriz parcialmente ordenada (ordenada). Heapify Medios, proporcione una matriz de montón desde una matriz no organizada; consulte los detalles a continuación.

Fusionar: Esto significa, formar un montón de unión de dos montones diferentes; consulte los detalles a continuación. Los dos montones deben ser máximos o ambos mínimos-tiempo. El nuevo montón está en conformidad con la propiedad del montón, mientras que los montones originales se conservan (no se borran).

MELD: Esto significa que une dos montones del mismo tipo para formar uno nuevo, manteniendo duplicados; consulte los detalles a continuación. El nuevo montón está en conformidad con la propiedad del montón, mientras que los montones originales se destruyen (borrados). La principal diferencia entre fusionar y fusionar es que para fusionar, un árbol se ajusta como un subárbol a la raíz del otro árbol, permitiendo valores duplicados en el nuevo árbol, mientras se fusiona, se forma un nuevo árbol de montón, eliminando los duplicados. No hay necesidad de mantener los dos montones originales con fusión.

Operaciones básicas de montón

find_max (find_min): localice el valor máximo en la matriz máxima y devuelva una copia, o ubique el valor mínimo en la matriz de mínimo y devuelva una copia.

Insertar: Agregue un nuevo elemento a la matriz de montón y reorganice la matriz para que se mantenga la propiedad del montón del diagrama.

Extract_max (Extract_min): Localice el valor máximo en la matriz máxima de montón, retire y devuélvalo; o localizar el valor mínimo en la matriz de mínimo, retírelo y devuélvelo.

delete_max (delete_min): localice el nodo raíz de un metal máximo, que es el primer elemento de la matriz máxima-heap, retírelo sin necesariamente devolverlo; o localizar el nodo raíz de un Min-HeAP, que es el primer elemento de la matriz MIN-Weap, retírelo sin necesariamente devolverlo;

Reemplace: Localice el nodo raíz de cualquier montón, retírelo y reemplácelo con uno nuevo. No importa si se devuelve la vieja raíz.

Operaciones internas del montón

aumentar_key (disminuir_key): aumente el valor de cualquier nodo para un máximo de montaje y reorganización para que se mantenga la propiedad del montón, o disminuya el valor de cualquier nodo para un mínimo-montón y reorganizar para que la propiedad del montón se mantenga.

Eliminar: elimine cualquier nodo, luego se reorganice, de modo que la propiedad del montón se mantenga para el máximo-montón o un mínimo-montón.

Shift_Up: Mueva un nodo hacia arriba en un máximo de montón o mínimo de tiempo mientras sea necesario, reorganizándose para mantener la propiedad del montón.

Shift_down: mueva un nodo hacia abajo en un máximo de montón o mínimo de tiempo mientras sea necesario, reorganizándose para mantener la propiedad del montón.

Inspección de un montón

Tamaño: Esto devuelve el número de claves (valores) en un montón; no incluye las ubicaciones vacías de la matriz de montón. Un montón puede representarse por código, como en el diagrama o con una matriz.

esta vacio: Esto devuelve boolean verdadero si no hay nodo en un montón o falso booleano si el montón tiene al menos un nodo.

Tamizar en un montón

Hay Sift-Up y Sift Down:

Sift-up: Esto significa intercambiar un nodo con su padre. Si la propiedad del montón no está satisfecha, intercambie al padre con su propio padre. Continúe de esta manera en el camino hasta que la propiedad del montón esté satisfecha. El procedimiento podría llegar a la raíz.

Sift-down: Esto significa intercambiar un nodo de gran valor con el más pequeño de sus dos hijos (o un niño por un montón casi completo). Si la propiedad del montón no está satisfecha, cambie el nodo inferior con el nodo más pequeño de sus propios dos hijos. Continúe de esta manera en el camino hasta que la propiedad del montón esté satisfecha. El procedimiento podría llegar a una hoja.

Estampado

Heapify significa ordenar una matriz sin clasificar para que la propiedad del montón sea satisfecha para Max-Heap o Min-Heap. Esto significa que puede haber algunas ubicaciones vacías en la nueva matriz. El algoritmo básico para acumular un máximo de montón o mínimo es el siguiente:

- Si el nodo raíz es más extremo que cualquiera de los nodos de su hijo, cambie la raíz con el nodo infantil menos extremo.

- Repita este paso con los nodos de los niños en un esquema de recorrido de árbol de pedido anticipado.

El árbol final es un árbol de montón que satisface la propiedad del montón. Un montón puede representarse como un diagrama de árbol o en una matriz. El montón resultante es un árbol parcialmente ordenado, yo.mi. una matriz parcialmente ordenada.

Detalles de la operación del montón

Esta sección del artículo proporciona los detalles de las operaciones de montón.

Creación de un montón Detalles

create_heap

Véase más arriba!

colocar

Véase más arriba

unir

Si las matrices de montón,

89, 85, 87, 84, 82, 79, 73, 80, 81 ,, 65, 69

y

89, 85, 84, 73, 79, 80, 83, 65, 68, 70, 71

se fusionan, el resultado sin duplicados puede ser,

89, 85, 87, 84, 82, 83, 81, 80, 79, 73, 68, 65, 69, 70, 71

Después de un tamiz. Observe que en la primera matriz, 82 no tiene hijos. En la matriz resultante, está en el índice 4; y sus ubicaciones en el índice 2 (4)+1 = 9 y 2 (4)+2 = 10 están vacantes. Esto significa que tampoco tiene hijos en el nuevo diagrama de árboles. Los dos montones originales no deben eliminarse ya que su información no está realmente en el nuevo montón (nueva matriz). El algoritmo básico para fusionar montones del mismo tipo es el siguiente:

- Une una matriz al final de la otra matriz.

- Heapify está eliminando los duplicados, asegurándose de que los nodos que no tuvieran hijos en los montones originales, aún no tengan hijos en el nuevo montón.

fustrar

El algoritmo para fusionar dos montones del mismo tipo (ya sea dos o dos min-) es el siguiente:

- Compare los dos nodos raíz.

- Haz la raíz menos extrema y el resto de su árbol (subárbol), el segundo hijo de la raíz extrema.

- Tamizar el niño callejero de la raíz de ahora el subárbol extremo, hacia abajo en el subárbol extremo.

El montón resultante todavía está en conformidad con la propiedad del montón, mientras que los montones originales se destruyen (borrados). Los montones originales pueden ser destruidos porque toda la información que poseían todavía está en el nuevo montón.

Operaciones básicas de montón

find_max (find_min)

Esto significa localizar el valor máximo en la matriz de alta hora y devolver una copia, o ubicar el valor mínimo en la matriz de mínimo y devolver una copia. Una matriz de montón por definición ya satisface la propiedad del montón. Entonces, solo devuelve una copia del primer elemento de la matriz.

insertar

Esto significa agregar un nuevo elemento a la matriz de montón y reorganizar la matriz para que se mantenga la propiedad del montón del diagrama (satisfecho). El algoritmo para hacer esto para ambos tipos de montones es el siguiente:

- Suponga un árbol binario completo. Esto significa que la matriz debe llenarse al final con ubicaciones vacías si es necesario. El número total de nodos de un montón completo es 1, o 3 o 7 o 15 o 31, etc.; Sigue duplicando y agregando 1.

- Coloque el nodo en la ubicación vacía más adecuada por magnitud, hacia el extremo del montón (hacia el final de la matriz de montón). Si no hay una ubicación vacía, comience una nueva fila desde la parte inferior izquierda.

- Sift uprie si es necesario, hasta que la propiedad del montón esté satisfecha.

Extract_max (Extract_min)

Localice el valor máximo en la matriz máxima de montón, retire y devuélvalo; o localizar el valor mínimo en la matriz de mínimo, retírelo y devuélvelo. El algoritmo para extraer_max (extract_min) es el siguiente:

- Eliminar el nodo raíz.

- Tome (elimine) el nodo más derecho a la derecha (último nodo en la matriz) y colóquelo en la raíz.

- Supcione según corresponda, hasta que la propiedad del montón esté satisfecha.

delete_max (delete_min)

Localice el nodo raíz de un máximo de metra, que es el primer elemento de la matriz de montaje máximo, retírelo sin necesariamente devolverlo; o localizar el nodo raíz de un mínimo-montaje, que es el primer elemento de la matriz de mínimo, retírelo sin devolverlo necesariamente. El algoritmo para eliminar el nodo raíz es el siguiente:

- Eliminar el nodo raíz.

- Tome (elimine) el nodo más derecho a la derecha (último nodo en la matriz) y colóquelo en la raíz.

- Supcione según corresponda, hasta que la propiedad del montón esté satisfecha.

reemplazar

Localice el nodo raíz de cualquier montón, retírelo y reemplácelo con el nuevo. No importa si se devuelve la vieja raíz. Sift hacia abajo si corresponde, hasta que la propiedad del montón esté satisfecha.

Operaciones internas del montón

aumentar_key (disminución_key)

Aumente el valor de cualquier nodo para un máximo de metra y reorganización para que se mantenga la propiedad del montón, o disminuya el valor de cualquier nodo para un mínimo y reorganización para que la propiedad del montón se mantenga. Sift hacia arriba o hacia abajo según corresponda, hasta que la propiedad del montón esté satisfecha.

borrar

Retire el nodo de interés, luego se reorganice, de modo que la propiedad del montón se mantenga para el máximo-montón o un mínimo-montón. El algoritmo para eliminar un nodo es el siguiente:

- Eliminar el nodo de interés.

- Tome (elimine) el nodo más alto a la derecha (último nodo en la matriz) y coloque en el índice del nodo eliminado. Si el nodo eliminado es en la última fila, entonces esto puede no ser necesario.

- Sift hacia arriba o hacia abajo según corresponda, hasta que la propiedad del montón esté satisfecha.

Shift_Up

Mueva un nodo hacia arriba en un máximo de montón o mínimo de tiempo mientras sea necesario, reorganizándose para mantener la propiedad del montón-Sift hacia arriba.

shift_down

Mueva un nodo hacia abajo en un máximo de montón o mínimo de tiempo mientras sea necesario, reorganizándose para mantener la propiedad del montón-Sift hacia abajo.

Inspección de un montón

tamaño

Véase más arriba!

esta vacio

Véase más arriba!

Otras clases de montones

El montón descrito en este artículo puede considerarse como el montón principal (general). Hay otras clases de montones. Sin embargo, los dos que debes saber más allá de esto son el montón binario y el montón D-ary.

Montón binario

El montón binario es similar a este montón principal, pero con más restricciones. En particular, el montón binario debe ser un árbol completo. No confunda entre un árbol completo y un árbol completo.

montón de d-ary

Un montón binario es un montón de 2 oraciones. Un montón donde cada nodo tiene 3 hijos es un montón de 3 días. Un montón donde cada nodo tiene 4 hijos es un montón de 4 días, y así sucesivamente. Un montón de D-oral tiene otras restricciones.

Conclusión

Un montón es un árbol binario completo o casi completo, que satisface la propiedad del montón. La propiedad del montón tiene 2 alternativas: para un máximo de montón, un padre debe ser igual o mayor en valor que los niños inmediatos; Para un mínimo de tiempo, un padre debe ser igual o menos en valor que los niños inmediatos. Un montón se puede representar como un árbol o en una matriz. Cuando se representa en una matriz, el nodo raíz es el primer nodo de la matriz; y si un nodo está en el índice n, su primer hijo en la matriz está en el índice 2n+1 y su próximo hijo está en el índice 2n+2. Un montón tiene ciertas operaciones que se realizan en la matriz.

Chrys