Almacenamiento básico del montón
1. Concepto e introducción
El montón (Heap) es un término general para un tipo especial de estructuras de datos en ciencias de la computación.
Un montón suele ser un objeto de arreglo que puede considerarse como un árbol binario completo.
El montón cumple las siguientes propiedades:
- El valor de un nodo en el montón siempre es no mayor (o no menor) que el valor de su nodo padre.
- El montón siempre es un árbol binario completo.
2. Instrucciones de aplicación
El montón utiliza la estructura de un árbol binario completo para mantener un conjunto de datos y luego realizar operaciones relacionadas. La complejidad temporal de una operación general es deO(1)~O(logn)entre estos valores; el montón se utiliza generalmente para asignar y liberar dinámicamente los objetos utilizados por el programa.
Si se trata del escenario de uso de una cola de prioridad, con un arreglo normal o un arreglo ordenado, el peor caso esO(n^2)la estructura de datos del montón también puede mejorar la eficiencia de las operaciones de encolar y desencolar.
| Encolar | Desencolar | |
|---|---|---|
| Arreglo normal | O(1) | O(n) |
| Arreglo ordenado | O(n) | O(1) |
| montículo | O(logn) | O(log) |
3. Diagrama de estructura
El montón binario es un árbol binario completo, y el valor de un nodo en el montón nunca es mayor que el valor de su nodo padre. La profundidad de este árbol binario completo es k; excepto el nivel k, el número de nodos en todos los demás niveles (1 a k-1) alcanza el número máximo, y todos los nodos del nivel k están concentrados continuamente en el extremo izquierdo.
Cuando el nodo raíz del montón es el más grande, se denomina montón máximo, como se muestra en la siguiente figura:

Podemos usar un arreglo para almacenar el montón binario; los números a la derecha son los índices del arreglo.


Suponiendo que la posición del índice del elemento actual sea i, se puede obtener la regla:
parent(i) = i/2(取整) left child(i) = 2*i right child(i) = 2*i +1
4. Código de ejemplo en Java
Descargar el paquete de código fuente:Download
Código del archivo src/ejemplo/heap/MaxHeap.java:
/**
* Definición del montón
*/
public class MaxHeap<T> {
private T[] data;
private int count;
// Constructor, construye un montón vacío que puede contener capacity elementos
public MaxHeap(int capacity){
data = (T[])new Object[capacity+1];
count = 0;
}
// Devuelve el número de elementos en el montón
public int size(){
return count;
}
// Devuelve un valor booleano que indica si el montón está vacío
public boolean isEmpty(){
return count == 0;
}
// Prueba MaxHeap
public static void main(String[] args) {
MaxHeap<Integer> maxHeap = new MaxHeap<Integer>(100);
System.out.println(maxHeap.size());
}
}