A Montón es una estructura de datos de árbol binario completa que satisface la propiedad del montón: para cada nodo, el valor de sus hijos es menor o igual a su propio valor. Los montones se utilizan generalmente para implementar colas de prioridad, donde el elemento más pequeño (o más grande) siempre está en la raíz del árbol.

cola de prioridad

Estructura de datos del montón

Tabla de contenidos

• Tipos de montones
• Operaciones de montón
• ¿Qué es la estructura de datos del montón?

  A montón es una estructura de datos binaria basada en árbol que satisface la propiedad del montón: el valor de cada nodo es mayor o igual que el valor de sus hijos. Esta propiedad garantiza que el nodo raíz contenga el máximo o mínimo valor (dependiendo del tipo de montón), y los valores disminuyen o aumentan a medida que avanza hacia abajo en el árbol.

  Tipos de montones

  Hay dos tipos principales de montones:

  
  
  
  
  • Montón máximo: El nodo raíz contiene el valor máximo y los valores disminuyen a medida que se avanza en el árbol.
  • Montón mínimo: El nodo raíz contiene el valor mínimo y los valores aumentan a medida que se avanza en el árbol.

  Operaciones de montón

  Las operaciones de montón comunes son:

  • Insertar : Agrega un nuevo elemento al montón mientras mantiene la propiedad del montón.
  • Extraer máximo/mínimo: Elimina el elemento máximo o mínimo del montón y lo devuelve.
  • amontonar : convierte un árbol binario arbitrario en un montón.

  Los montones se utilizan comúnmente para implementar colas de prioridad, donde los elementos se recuperan en función de su prioridad (valor máximo o mínimo).

• Heapsort es un algoritmo de clasificación que utiliza un montón para ordenar una matriz en orden ascendente o descendente.
• Los montones se utilizan en algoritmos gráficos como El algoritmo de Dijkstra y El algoritmo de Prim. para encontrar los caminos más cortos y los árboles de expansión mínima.

montón binario

Aplicaciones, ventajas y desventajas del montón

Tiempo Complejidad de construir un montón.

Comparación entre montón y árbol

Al construir un montón, ¿la estructura del montón es única?

Montón de Fibonacci

Montón izquierdista

Montón K-ary

Ordenar montón

Comprobar si un árbol binario determinado es un montón

¿Cómo comprobar si una matriz determinada representa un montón binario?

Ordenación de montón iterativo

K'th elemento más grande en una matriz

K'th elemento más pequeño/más grande en una matriz sin clasificar | Serie 1

Altura de un árbol binario completo (o Heap) con N nodos

Orden de montón para orden decreciente usando montón mínimo

Imprima todos los nodos menores que un valor x en un montón mínimo.

Árbol de torneos (árbol de ganadores) y montón binario

Conecte n cuerdas con un costo mínimo.

Máximo de elementos distintos después de eliminar k elementos

K combinaciones de suma máxima de dos matrices

Mediana del flujo de enteros en ejecución usando STL

Mediana en una secuencia de números enteros (enteros en ejecución)

K'ésimo elemento más grande en una corriente

Producto triplete más grande en una secuencia

Encuentre k números con más apariciones en la matriz dada

Convertir montón mínimo en montón máximo

Dado el recorrido del orden de nivel de un árbol binario, verifique si el árbol es un montón mínimo

Fusionar k matrices ordenadas | Serie 1

Ordenar números almacenados en diferentes máquinas

El menor trastorno de secuencia

Mayor trastorno de una secuencia

Diferencia máxima entre dos subconjuntos de m elementos

Convertir BST a montón mínimo

Fusionar dos Max Heaps binarios

K-ésimo subconjunto contiguo de suma más grande

Producto mínimo de k enteros en una matriz de enteros positivos

Reorganice los caracteres en una cadena de modo que no haya dos adyacentes iguales

Suma de todos los elementos entre k1'ésimo y k2'ésimo elemento más pequeño

Suma mínima de dos números formados a partir de dígitos de una matriz

Enlaces rápidos:

• Problemas de práctica en montón
• Recomendado:
  • Aprenda la estructura de datos y los algoritmos | Tutorial de DSA