Aquí hay una implementación de Java de un MIN-Weap, que incluye métodos para la inserción, extracción del elemento mínimo y operaciones de Heapify:
`` `Java
clase pública minheap {
privado int [] Heap;
tamaño privado int;
Capacidad privada int;
Public MinHeap (Int Capacidad) {
this.capacity =capacidad;
this.heap =new int [capacidad + 1]; // El índice 0 no se usa
this.size =0;
}
Public boolean isEtimty () {
tamaño de retorno ==0;
}
public boolean isfull () {
tamaño de retorno ==Capacidad;
}
Private Int Parent (int i) {
regresar i / 2;
}
Private int Left (int i) {
regresar 2 * i;
}
Private int Right (int i) {
return 2 * i + 1;
}
swap vacío privado (int i, int j) {
int temp =Heap [i];
Heap [i] =Heap [J];
montón [j] =temp;
}
Public void Insert (int key) {
if (isfull ()) {
tirar nueva ilegalstateException ("el montón está lleno");
}
tamaño ++;
montón [tamaño] =clave;
int i =tamaño;
while (i> 1 &&Heap [parent (i)]> Heap [i]) {// propiedad de mínimo-heap
intercambio (i, padre (i));
i =padre (i);
}
}
public int ExtractMin () {
if (isEmpty ()) {
tirar nueva IllegalStateException ("el montón está vacío");
}
int root =Heap [1];
montón [1] =montón [tamaño];
tamaño--;
Heapify (1);
raíz de retorno;
}
Private void Heapify (int i) {
int más pequeño =i;
int l =izquierda (i);
int r =right (i);
if (l <=size &&Heap [l]
}
if (r <=size &&Heap [r]
}
if (más pequeño! =i) {
intercambio (i, más pequeño);
Heapify (más pequeño);
}
}
public void PrintHeap () {
para (int i =1; i <=size; i ++) {
System.out.print (Heap [i] + "");
}
System.out.println ();
}
public static void main (string [] args) {
Minheap minheap =new Minheap (10);
minheap.insert (3);
minheap.insert (2);
minheap.insert (15);
minheap.insert (5);
minheap.insert (4);
minheap.insert (45);
System.out.println ("Minheap Array:");
minheap.printheap ();
System.out.println ("Extract Min:" + minheap.extractmin ());
System.out.println ("Después de extraer min:");
minheap.printheap ();
}
}
`` `` ``
Este código incluye:
* Constructor: Inicializa la matriz de montón con una capacidad dada. Tenga en cuenta que el índice 0 no se usa.
* `isEtimty ()` y `isfull ()`: Verifique el estado del montón.
* `parent ()`, `izquierd ()`, `right ()`: Ayudante funciona para obtener los índices de nodos de padres e hijos.
* `swap ()`: Intercambia dos elementos en la matriz.
* `insert ()`: Inserta un nuevo elemento en el montón, manteniendo la propiedad MIN-Weap.
* `ExtractMin ()`: Elimina y devuelve el elemento mínimo (raíz), manteniendo la propiedad MIN-HAEP usando `Heapify ()`.
* `Heapify ()`: Restaura la propiedad MIN-HeAP después de eliminar o insertar un elemento. Compara recursivamente un elemento con sus hijos y cambia si es necesario.
* `impresheap ()`: Una función de ayudante para la demostración.
Recuerde manejar posibles excepciones, como tratar de extraer de un montón vacío o insertar en uno completo. Este ejemplo usa valores enteros; Puede adaptarlo fácilmente a otros tipos de datos utilizando un parámetro de tipo genérico. Para montones más grandes, considere usar una estrategia de cambio de tamaño más sofisticada para evitar la limitación de capacidad fija.