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.

 EncolarDesencolar
Arreglo normalO(1)O(n)
Arreglo ordenadoO(n)O(1)
montículoO(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:

package ejemplo.heap;

/**
* 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());
    }
}
Otras extensiones