Introducción a la ordenación del montón en Java
Heapsort en Java es una técnica de clasificación basada en comparación, donde se utiliza la estructura de datos Binary Heap. Esta ordenación es casi la misma que la ordenación por selección, donde se seleccionará el elemento más grande y se colocará al final y el proceso se repetirá para todos los elementos. Para entender la ordenación del montón, veamos qué ordenación del montón binario en Java.
- Estructura de datos basada en árboles.
- Árbol binario completo.
- Puede tener hasta dos hijos.
- El valor en el nodo raíz puede ser mayor (Max Heap) o Menor (Min Heap)
¿Cómo funciona Heap Sort en Java?
Antes de pasar al algoritmo, veamos qué es Heapify.
Heapify
Después de crear un montón con los datos de entrada, es posible que no se cumpla la propiedad del montón. Para lograrlo, se utilizará una función llamada heapify para ajustar los nodos del montón. Si queremos crear un montón máximo, el elemento actual se comparará con sus elementos secundarios y si el valor de elementos secundarios es mayor que el elemento actual, el intercambio se realizará con el elemento más grande en un elemento secundario izquierdo o derecho. Del mismo modo, si es necesario crear min-heap, el intercambio se realizará con el elemento más pequeño en el elemento secundario izquierdo o derecho. Por ejemplo, la siguiente es nuestra matriz de entrada,
Podemos considerar esto como un árbol en lugar de una matriz. El primer elemento será root, el segundo será el hijo izquierdo de root, el tercer elemento será el hijo derecho de root, y así sucesivamente.
Para transformar el montón en un árbol, atraviese el árbol en una dirección ascendente. Como los nodos de la hoja no tienen hijos, veamos el siguiente nivel. es decir, es 5 y 7.
Podemos comenzar a las 5 como está a la izquierda. Aquí, 5 tiene dos hijos: 9 y 4, donde 9 es mayor que el nodo padre 5. Para agrandar los padres, intercambiaremos 5 y 9. Después de intercambiar, el árbol será como se muestra a continuación.
Pasemos al siguiente elemento 7, donde 8 y 2 son los hijos. Similar a los elementos 9 y 4, 7 y 8 se intercambiarán como en el árbol de abajo.
Finalmente, 3 tiene dos hijos: 9 y 8, donde 9 es mayor entre los hijos y la raíz. Por lo tanto, el intercambio de 3 y 9 se realizará para aumentar la raíz. Repita el proceso hasta que se forme un montón válido como se muestra a continuación.
Algoritmo para la ordenación del montón en orden ascendente
- Crear un montón máximo con los datos de entrada
- Reemplace el último elemento con el elemento más grande en el montón
- Heapify the Tree
- Repita el proceso hasta que la matriz esté ordenada
Algoritmo para la ordenación del montón en orden descendente
- Crear un montón mínimo con los datos de entrada
- Reemplace el último elemento con el elemento más pequeño en el montón
- Heapify the Tree
- Repita el proceso hasta que la matriz esté ordenada
Ahora, intentemos ordenar el montón obtenido anteriormente en orden ascendente utilizando el algoritmo dado. Primero, elimine el elemento más grande. es decir, raíz y reemplazarlo con el último elemento.
Ahora, heapify el árbol formado e inserte el elemento eliminado en el último de la matriz como se muestra a continuación
Nuevamente, elimine el elemento raíz, reemplácelo con el último elemento y aplíquelo.
Inserte el elemento eliminado en la posición vacante. Ahora puede ver que se está ordenando el final de la matriz.
Ahora, retire el elemento 7 y reemplácelo con 2.
Heapify el árbol, como se muestra a continuación.
Repita el proceso hasta que se ordene la matriz. Retirar el elemento 5.
Heapificando el árbol.
Retirar el elemento 4.
Heapfying otra vez.
Por fin, se formará una matriz ordenada como esta.
Ejemplos para implementar la ordenación del montón en Java
Ahora, veamos el código fuente de Heap Sort en Java
//Java program to sort the elements using Heap sort
import java.util.Arrays;
public class HeapSort (
public void sort(int array()) (
int size = array.length; //Assigning the length of array in a variable
// Create heap
for (int i = size / 2 - 1; i >= 0; i--)
heapify(array, size, i);
//Find the maximum element and replace it with the last element in the array
for (int i=size-1; i>=0; i--) (
int x = array(0);//largest element(It is available in the root)
array(0) = array(i);
array(i) = x;
// Recursively call heapify until a heap is formed
heapify(array, i, 0);
)
)
// Heapify function
void heapify(int array(), int SizeofHeap, int i) (
int largestelement = i; // Set largest element as root
int leftChild = 2*i + 1; // index of left child = 2*i + 1
int rightChild = 2*i + 2; //index of right child = 2*i + 2
// left child is greater than root
if (leftChild array(largestelement))
largestelement = leftChild ;
//right child is greater than largest
if (rightChild array(largestelement))
largestelement = rightChild ;
// If largestelement is not root
if (largestelement != i) (
int temp = array(i);
array(i) = array(largestelement);
array(largestelement) = temp;
// Recursive call to heapify the sub-tree
heapify(array, SizeofHeap, largestelement);
)
)
public static void main(String args()) (
int array() = (3, 5, 7, 9, 4, 8, 2);
System. out .println("Input array is: " + Arrays. toString (array));
HeapSort obj = new HeapSort();
obj.sort(array);
System. out .println("Sorted array is : " + Arrays. toString (array));
)
)
Salida
Conclusión
Heap Sort es una técnica de ordenación que depende de la estructura de datos binarios del montón. Es casi similar al ordenamiento por selección y no utiliza matrices separadas para la ordenación y el almacenamiento dinámico.
Artículo recomendado
Esta ha sido una guía de Heap Sort en Java. Aquí discutimos el algoritmo de clasificación de trabajo con orden ascendente y descendente y ejemplos con código de muestra. También puede consultar nuestros otros artículos sugeridos para obtener más información:
- Funciones matemáticas de JavaScript
- Diseño en Java
- Compiladores Java
- Guía para ordenar por fusión en Java
- Guía para ordenar el montón en C
- Ejemplos de ordenación del montón en C ++