Este artículo le brindará una descripción general completa del funcionamiento de la ordenación del montón y luego aprenderemos a implementar un montón binario en Java.
Aquí está la agenda de este artículo:
- ¿Qué es el tipo de pila?
- Montón máximo
- Montón mínimo
- Implementación de montón en Java
- Diagrama
- Código
¡Vamos a empezar!
¿Qué es el tipo de pila?
Heap es básicamente una estructura de datos basada en árboles. Tiene nodos. El nodo se compone de ciertos elementos. Cada nodo contiene un elemento.
Los nodos pueden tener hijos. Si en caso de que no haya hijos, se llama Hoja.
Hay dos reglas a seguir:
- El valor de cada nodo debe ser menor o igual a todos los valores almacenados en sus hijos.
- Tiene la menor altura posible.
Los montones son extremadamente eficientes para extraer elelemento menor o mayor.
¡Pasemos al montón mínimo ahora!
conversión de tipo c ++
Montón mínimo
Min heap es un árbol binario completo en el que el valor del elemento raíz es menor o igual que cualquiera de los elementos secundarios.
Representación de min heap
Arr [(i-1) / 2]: esto devolverá el nodo padre.
Arr [(2 * i) + 1]: esto devolverá el nodo hijo izquierdo.
Arr [(2 * i) + 2]: esto devolverá el nodo hijo correcto.
Hay ciertos métodos de Min Heap:
- insertar(): Se agrega una nueva clave al final del árbol. En caso de que la nueva clave sea mayor que la principal, entonces no hay necesidad de hacer nada, de lo contrario, tenemos que recorrer para configurar la propiedad del montón.
- getMin (): este método ayuda a devolver el elemento raíz.
- extractMin(): este método devuelve el mínimoelemento.
Pasando a Max heap ahora.
Montón máximo
Max heap es un árbol binario completo en el que el valor del elemento raíz es mayor o igual que cualquiera de los elementos secundarios.
¡Max heap también consta de varios métodos!
- Insertar (): insertará un elemento en el montón.
- Eliminar() : eliminará un elemento del montón.
- FindMax (): encontrará el elemento máximo del montón.
- printHeap (): Imprimirá el contenido del montón
Ahora déjame mostrarte la implementación del montón a través de un diagrama y luego un Javacódigo.
Implementación de montón en Java
Diagrama:
establecer la ruta de Java en Windows
El diagrama de arriba muestra el montón binario en Java. Como ha aprendido que hay dos montones: Min heap y Max heap, aquí hay un diagrama:
Ahora, pasando al siguiente segmento, veremos cómo implementar un montón binario en Java.
Código:
public class BinaryHeap {private static final int d = 2 private int [] heap private int heapSize / ** * Esto inicializará nuestro montón con el tamaño predeterminado. * / public BinaryHeap (int capacidad) {heapSize = 0 heap = new int [capacidad + 1] Arrays.fill (heap, -1)} / ** * Esto comprobará si el montón está vacío o no * Complejidad: O ( 1) * / public boolean isEmpty () {return heapSize == 0} / ** * Esto verificará si el montón está lleno o no * Complexity: O (1) * / public boolean isFull () {return heapSize == heap .length} private int parent (int i) {return (i-1) / d} private int kthChild (int i, int k) {return d * i + k} / ** * Esto insertará un nuevo elemento en el montón * Complejidad: O (log N) * En el peor de los casos, tenemos que recorrer hasta la raíz * / public void insert (int x) {if (isFull ()) throw new NoSuchElementException ('Heap is full, No space to insert nuevo elemento ') heap [heapSize ++] = x heapifyUp (heapSize-1)} / ** * Esto eliminará el elemento en el índice x * Complexity: O (log N) * * / public int delete (int x) {if (isEmpty ()) lanzar una nueva NoSuchElementException ('El montón está vacío, no hay elemento para eliminar') int clave = montón [x] montón [x] = montón [tamaño de montón -1] tamaño de montón-- heapifyDown (x) retu rn key} / ** * Este método se usa para mantener la propiedad del montón mientras se inserta un elemento. * * / private void heapifyUp (int i) {int temp = heap [i] while (i> 0 && temp> heap [parent (i)]) {heap [i] = heap [parent (i)] i = parent (i)} heap [i] = temp} / ** * Este método se usa para mantener la propiedad del montón mientras se elimina un elemento. * * / private void heapifyDown (int i) {int child int temp = heap [i] while (kthChild (i, 1)heap [rightChild]? leftChild: rightChild} / ** * Este método se usa para imprimir todos los elementos del montón * * / public void printHeap () {System.out.print ('nHeap =') para (int i = 0 iCon esto, llegamos al final de este artículo sobre Binary Heap en Java. Revisar la por Edureka, una empresa de aprendizaje en línea de confianza con una red de más de 250.000 alumnos satisfechos repartidos por todo el mundo. El curso de formación y certificación Java J2EE y SOA de Edureka está diseñado para estudiantes y profesionales que desean ser desarrolladores de Java. El curso está diseñado para darle una ventaja en la programación de Java y capacitarlo para los conceptos básicos y avanzados de Java junto con varios marcos de Java como Hibernate y Spring.
Tienes una pregunta para nosotros? Menciónelo en la sección de comentarios de este blog 'Java ArrayList' y nos comunicaremos con usted lo antes posible.