© metamorworks/Shutterstock.com
Al clasificar una matriz de datos, es crucial familiarizarse con los algoritmos de clasificación. En las estructuras de datos, la clasificación consiste en organizar los datos en un formato específico basado en una relación lineal entre los elementos de datos.
La clasificación es esencial, ya que la búsqueda de datos se puede optimizar a un nivel muy alto cuando los datos se clasifican en un formato determinado. Además, la clasificación puede representar datos en un formato más legible. Tenemos una amplia gama de algoritmos de clasificación, pero en este artículo examinaremos qué es la clasificación Heap y cómo usarla. ¡Vamos directamente a ello!
Qué es Heap Sort: una definición exacta
Heap sort es un algoritmo de clasificación bien conocido y eficiente. Es un concepto que se utiliza para ordenar datos de matriz eliminando elementos uno por uno del montón, un árbol binario completo, parte de la lista, y luego insertándolos en la parte ordenada de la lista.
Ordenar montón básicamente tiene dos fases involucradas:
Crear un montón, ya sea un montón máximo o un montón mínimo usando elementos de una matriz específica. Eliminar recursivamente el elemento raíz del montón creado en la primera fase.
¿Cómo funciona el algoritmo de clasificación de almacenamiento dinámico?
Así es como se implementa el algoritmo de clasificación de almacenamiento dinámico:
Cree un almacenamiento dinámico máximo para almacenar datos de la lista sin clasificar. Saque el valor más grande de el montón e insértelo en una lista ordenada. Intercambie la raíz del montón con el último elemento de la lista y luego vuelva a equilibrar el montón. Una vez que el montón máximo esté completamente vacío, devuelva la lista ordenada.
Aquí está el algoritmo
HeapSort(arr)
CreateMaxHeap(arr)
for i=length(arr) a 2
intercambiar arr[1] por arr[i]
heap_size[arr]=heap_size[arr] ? 1
MaxHeapify(arr,1)
Fin
Examinemos un poco más los pasos.
Paso 1: crear un máximo-heap
CreateMaxHeap(arr)
heap_size(arr)=longitud(arr)
for i=longitud(arr)/2 a 1
MaxHeapify(arr,i)
End
En este algoritmo, necesitaremos construir un montón máximo. Como todos sabemos, en un montón máximo, el valor más grande es el valor raíz. Cada nodo principal debe tener un valor mayor que sus hijos asociados.
Imagínese que tuviéramos la siguiente lista de valores sin clasificar:
[14, 11, 2, 20, 3, 10 , 3]
Al colocar nuestros valores en una estructura de datos de pila máxima, así es como se vería nuestra lista:
[20, 11, 14, 2, 10, 5 , 3]
Podemos presentar el montón máximo anterior de esta manera:
Presentación de un montón máximo.
©”TNGD”.com
Paso 2: Quitar la raíz del montón
Para ordenar los datos, extraeremos y eliminaremos repetidamente el valor más grande del montón hasta que esté vacío. Si seguimos los principios de los montones, podemos anticipar que el valor más grande estará ubicado en la raíz del montón.
Después de eliminar el valor más grande, no podemos simplemente abandonar el montón sin una raíz, porque resultaría en la desconexión de dos nodos. En su lugar, podemos intercambiar el nodo raíz con el último elemento del montón. Dado que el último elemento no tiene elementos secundarios, se puede eliminar fácilmente del montón.
Sin embargo, este paso genera un problema importante. Al intercambiar los dos elementos, el nodo raíz ya no es el más grande del montón. Será necesario reestructurar el montón para garantizar que esté equilibrado.
Paso 3: acumular hacia abajo (restaurar el montón)
El valor raíz no es el valor más grande, el principio del montón ha sido violado ya que el padre debe tener un valor mayor que el valor de los hijos.
Sin embargo, ¡hay una solución a este problema! Tendremos que acumular, lo que implica agregar un valor al final del montón y avanzar en la estructura de datos hasta que encuentre la posición adecuada. Para colmo, compara el nuevo valor raíz con sus hijos, selecciona el hijo con el valor mayor y lo intercambia con el valor raíz. Avanza por el montón hasta que esté equilibrado.
Ilustración del proceso heapify down.
©”TNGD”.com
En el ejemplo anterior, intercambia el valor raíz original 20 con 3, el hijo más a la derecha. Teniendo 3 como la nueva raíz, compare su valor con su valor secundario 14, y dado que es mayor que 3, intercámbielos para hacer que 14 sea la nueva raíz. Luego, compare 3 con su nuevo hijo 5, y dado que 5 es mayor que 3, intercámbielos para que 5 sea el nuevo valor principal. Dado que no hay otros hijos para comparar con 3, el montón ahora está equilibrado.
Paso 4: Repita
Tendrá que repetir el procedimiento de intercambiar la raíz y la última eliminando el valor más grande y reequilibrando el montón siempre que la estructura de datos contenga un tamaño mayor que 1. Cuando se cumple este criterio, tendrá un conjunto ordenado de valores.
Complejidad de clasificación de montón
Complejidad de tiempo
Aquí está la complejidad de tiempo de Heap Sort en el mejor de los casos, el caso promedio y el peor de los casos.
Best Case Complexity: Ocurre cuando la matriz ya está ordenada, es decir, no se requiere ordenar. O(n log n) es la complejidad de tiempo en el mejor de los casos de la ordenación del montón. Complejidad de caso promedio: Ocurre cuando los elementos en la matriz no están dispuestos en un orden ascendente o descendente adecuado, lo que resulta en una orden desordenado. O(n log n) es la complejidad de tiempo de caso promedio de la ordenación del montón. Complejidad del peor caso: esto sucede cuando necesita ordenar los elementos de la matriz en orden inverso, lo que significa que si los elementos están inicialmente en orden descendente orden, tendrá que ordenarlos en orden ascendente. O(n log n) es la complejidad de tiempo en el peor de los casos de clasificación de almacenamiento dinámico.
Complejidad del espacio
La complejidad del espacio del ordenamiento del montón es O(1)
¿Cómo se implementa el algoritmo de ordenación en montón?
Así es como se implementa la ordenación en montón en el lenguaje de programación Java.
//Para acumular un subárbol. Aquí”i”es el índice del nodo raíz en arr[], y”x”es el tamaño del almacenamiento dinámico
public class HeapSort {
public static void sort(int[] arr) {
int x=arr.length;
//reorganizar matriz (construir montón)
for (int i=x/2 – 1; i >=0; i–)
heapify(arr, x, i);
//extrae un elemento uno a uno del montón
for (int i=x – 1; i > 0; i–) {
//mover la raíz inicial al final
int temp=arr[0];
arr[0]=arr[i];
arr[i]=temp;
//llamar a la función max heapify en el montón reducido
heapify(arr, i, 0);
}
}
static void heapify(int[] arr, int x, int i) {
int mayor=i;//inicializar el mayor como raíz
int l=2 * i + 1;//izquierda
int r=2 * i + 2;//derecho
//si el hijo izquierdo es más grande que la raíz
if (l x && arr[l] > arr[mayor])
mayor=l;
//si el hijo derecho es más grande que el más grande hasta ahora
if (r x && arr[r] > arr[mayor])
mayor=r;
//si el mayor no es la raíz
if (mayor !=i){
int swap=arr[i];
arr[i]=arr[el más grande];
arr[el más grande]=swap;
//agrupar repetidamente el subárbol afectado
heapify(arr, x, mayor);
}
}
//una función para imprimir una matriz de tamaño x
static void printArray(int[]) {
int x=arr.length;
for (int i=0; i x; ++i)
System.out.print(arr[i] + ” “);
System.out.println();
}
//Código del controlador
public static void main (String[] args) {
int[] arr={ 13, 12, 14, 6, 7, 8 };
sort(arr);
System.out.println(“La matriz ordenada es”);
printArray(arr);
}
}
Salida
Esta es la matriz de enteros ordenados en orden ascendente.
La matriz ordenada es
6, 7, 8, 12, 13, 14
Pros y contras del algoritmo de ordenación en montón
Ventajas
Eficiencia: este algoritmo de clasificación es muy eficiente ya que el tiempo requerido para clasificar un montón aumenta logarítmicamente, mientras que en otros algoritmos el tiempo crece exponencialmente más lento a medida que aumentan los elementos de clasificación.Simplicidad: en comparación con otros algoritmos igualmente eficientes, es más simple ya que no utiliza principios informáticos avanzados como la recursividad. Uso de memoria: la clasificación en montón utiliza una memoria mínima para contener la lista inicial de elementos que se clasificarán , y no se requiere espacio de memoria adicional para funcionar.
Contras
Caro: la clasificación de montones es costosa.Inestable: la clasificación de montones no es confiable, ya que podría reorganizar el orden relevante de los elementos.Ineficiente: cuando se trata de datos muy complejos, Heap Sort no es muy eficiente.
Aplicaciones de la clasificación en montón
Es posible que haya encontrado el algoritmo de Dijkstra, que utiliza la clasificación en montón para determinar la ruta más corta. En la estructura de datos, la ordenación del montón permite la recuperación rápida del valor más pequeño (más corto) o más grande (más largo). Tiene varias aplicaciones, incluida la determinación del orden en las estadísticas, la gestión de las colas de prioridad en el algoritmo de Prim (también conocido como árbol de expansión mínimo) y la realización de la codificación Huffman o la compresión de datos.
Del mismo modo, varios sistemas operativos utilizan Heap algoritmo de clasificación para la gestión de trabajos y procesos, ya que se basa en una cola de prioridad.
En un escenario de la vida real, la clasificación por heap se puede aplicar en una tienda de tarjetas SIM, donde tenemos una larga cola de clientes esperando ser atendido. Se puede priorizar a los clientes que necesitan pagar sus facturas, ya que su trabajo lleva un tiempo mínimo. Este enfoque ahorrará tiempo a muchos clientes y evitará demoras innecesarias, lo que generará una experiencia más eficiente y satisfactoria para todos.
Conclusión
Cada algoritmo de clasificación o búsqueda tiene sus ventajas y desventajas. , y Heap Sorting no es una excepción. Sin embargo, las desventajas de Heap Sort son relativamente mínimas. Por ejemplo, no requiere ningún espacio de memoria adicional más allá del que ya está asignado.
El tiempo es otro factor. Se encuentra que la complejidad del tiempo se determina utilizando nlog(n), pero la ordenación real del almacenamiento dinámico es menor que O(nlog(n)). Esto se debe a que la extracción desde el almacenamiento dinámico reduce el tamaño, lo que lleva menos tiempo a medida que avanza el proceso. Por lo tanto, Heap Sort es ampliamente considerado como uno de los”mejores”algoritmos de clasificación en el ámbito de la estructura de datos por varias razones.
¿Qué es Heap Sort y cómo se usa? Preguntas frecuentes (FAQ)
¿Qué significa heapify?
Heapify es el proceso de creación de una estructura de datos en montón a partir de una representación de matriz de un binario árbol. Este proceso se puede utilizar para crear Max-Heap o Min-Heap. Comienza desde el último índice del nodo que no es hoja en el árbol binario, cuyo índice está dado por n/2 – 1. Heapify se implementa usando recursividad.
¿Cómo funciona Heap Sort?
Heap sort es un algoritmo de clasificación basado en la comparación. Funciona moviendo los elementos más grandes de la región no ordenada a la región ordenada, reduciendo así la región no ordenada. Heap sort visualiza los elementos de la matriz como un montón, y es conocido por tener un tiempo de ejecución óptimo. Este algoritmo es útil cuando desea mantener el orden mientras extrae el elemento mínimo o máximo de la matriz.
¿Cómo se “amontona” un árbol?
Para remodelar o apilar un árbol binario, comience seleccionando un nodo como el nodo raíz del subárbol. Luego, compara el valor del nodo raíz con los valores de sus nodos secundarios izquierdo y derecho. Si alguno de los nodos secundarios tiene un valor mayor (en el caso de un montón máximo) o menor (en el caso de un montón mínimo) que el nodo raíz, intercambia los valores del nodo raíz y el nodo secundario con el valor mayor (o menor). Después de intercambiar los valores, acumula recursivamente el subárbol enraizado en el nodo secundario hasta que todo el subárbol satisface la propiedad del montón. Repite este proceso para cada nodo en el árbol hasta que todo el árbol satisfaga la propiedad del montón.
La complejidad de tiempo de heapify es O(log n), donde n es el número de nodos en el subárbol que se está acumulando.
¿Qué es un montón binario?
Un montón binario es una estructura de datos que se puede considerar como un árbol binario completo donde cada nodo principal está menor o igual que sus hijos (en un montón mínimo) o mayor o igual que sus hijos (en un montón máximo).
¿Cuáles son las ventajas del tipo de montón?
Las ventajas de la ordenación en montón incluyen su complejidad de tiempo de O(n log n), que es más rápido que otros algoritmos de ordenación populares, como la ordenación por burbuja y la ordenación por inserción. Además, la clasificación en montón ocupa poco espacio en la memoria, ya que solo requiere una cantidad constante de espacio adicional.
¿Cuáles son las desventajas de la clasificación en montón?
La Las desventajas de la ordenación en montón incluyen su propiedad de ordenación no estable, lo que significa que el orden relativo de elementos iguales puede no conservarse después de la ordenación. Además, la ordenación en montón no es muy eficiente para arreglos pequeños y su naturaleza recursiva puede conducir a un rendimiento más lento en algunas arquitecturas.