En informática , un montón es una estructura de datos especializada del tipo de árbol que satisface la propiedad del montón : si B es un nodo hijo del nodo A , entonces clave( A ) ≥ clave( B ). De ello se deduce que el elemento con la clave más grande es siempre el nodo raíz del montón, por lo que a veces estos montones se denominan montones máximos (alternativamente, si se invierte la comparación, el elemento más pequeño siempre será el nodo raíz, tales montones se denominan min-montones ). No existe ninguna restricción sobre cuántos nodos secundarios tiene cada nodo del montón, aunque en la práctica este número no suele ser más de dos. El montón es la implementación más eficiente de un tipo de datos abstracto llamado cola de prioridad . Los montones son cruciales en algunos algoritmos gráficos eficientes , como el algoritmo de Dijkstra en d-heaps y heapsort .
La estructura de datos del montón no debe confundirse con el concepto de montón en la asignación de memoria dinámica . El término se utilizó por primera vez específicamente para estructuras de datos. Algunos de los primeros lenguajes de programación populares, como LISP , proporcionaron una asignación de memoria dinámica utilizando la estructura de datos "montón", que dio su nombre a la cantidad de memoria asignada. [1] .
Los montones generalmente se implementan como matrices, lo que elimina la necesidad de punteros entre sus elementos.
Las siguientes operaciones generalmente se realizan en montones:
A continuación, se muestran estimaciones de la complejidad temporal de los cálculos para operaciones en ciertos tipos de montones. [1] Cuando un valor está marcado con un asterisco, la estimación se basa en el análisis de amortización (peor momento), de lo contrario, la estimación es el peor caso normal. O(F) da un límite superior asintótico, y Θ(F) es una estimación asintóticamente exacta (consulte la notación "O" grande y "o" pequeña ). Los nombres de operación se eligen para el montón mínimo.
(*) Tiempo de amortización
(**) Donde n es el tamaño del montón más grande
Tenga en cuenta que la "cola de Brodal" es una implementación de una cola de prioridad paralela desarrollada por un grupo dirigido por Gert Brodal. [3]
Las estructuras de datos de montón tienen muchos usos.
Un montón binario completo y casi completo se puede representar de una manera muy eficiente utilizando una matriz de índices . El primer (o último) elemento contendrá la raíz. Los siguientes dos elementos de la matriz contienen los nodos secundarios de la raíz. Los siguientes cuatro elementos contienen cuatro hijos de dos nodos que son hijos de la raíz, y así sucesivamente, por lo tanto, los hijos del nodo de nivel nse ubicarán en posiciones 2ny 2n+1para una matriz indexada desde uno, o en posiciones 2n+1y 2n+2para una matriz indexada desde cero Esto le permite moverse hacia arriba o hacia abajo en el árbol haciendo simples cálculos de índice de matriz. El equilibrio del montón se realiza reorganizando los elementos que están desordenados. Dado que podemos construir un montón usando una matriz sin memoria adicional (para nodos, por ejemplo), podemos usar heapsort para ordenar la matriz en su lugar.
| Estructuras de datos | |
|---|---|
| Liza | |
| Árboles | |
| cuenta | |
| Otro | |
| Aspectos de los sistemas operativos | |||||
|---|---|---|---|---|---|
| |||||
| Tipos |
| ||||
| Núcleo |
| ||||
| Gestión de procesos |
| ||||
| Gestión y direccionamiento de memoria | |||||
| Herramientas de carga e inicialización | |||||
| Caparazón | |||||
| Otro | |||||
| Categoría Wikimedia Commons Wikilibros Wikcionario | |||||