Algoritmo de clasificación de montón (con código en Python y C++)
sarah chen
¿Qué es el algoritmo de clasificación de montón?
Heap Sort es uno de los algoritmos de ordenamiento más populares y rápidos. Se basa en la estructura de datos de árbol binario completo. Buscaremos el elemento máximo y lo colocaremos en la parte superior del montón máximo. Lo colocaremos en el nodo principal del árbol binario.
Digamos que se da una matriz, datos = [10,5, 7, 9, 4, 11, 45, 17, 60].
En la matriz, si el índice i-ésimo (i=0,1,2,3…) es un nodo principal, entonces (2i+1) y (2i+2) serán los hijos izquierdo y derecho. Crear un árbol binario completo con esta matriz se verá así:
Realizaremos el proceso de heapificación desde el principio hasta el final de la matriz. Inicialmente, si convertimos la matriz en un árbol, se verá como se muestra arriba. Podemos ver que no mantiene ninguna propiedad de heap (min-heap o max-heap). Obtendremos la matriz ordenada realizando el proceso de heapificación para todos los nodos.
Aplicación de clasificación de montón
A continuación se muestran algunos usos del algoritmo de clasificación del montón:
- La construcción de "colas prioritarias" necesita clasificación en montón. Porque Heapsort mantiene el elemento ordenado después de realizar cada inserción.
- La estructura de datos del montón es eficiente para encontrar el kth elemento más grande en una matriz dada.
- El kernel de Linux utiliza el tipo de montón por defecto algoritmo de clasificación ya que tiene una complejidad espacial O (1).
Crear clasificación de montón con ejemplo
Aquí, construiremos un montón máximo a partir del siguiente árbol binario completo.
Los nodos de hoja son 17, 60, 4, 11 y 45. No tienen ningún nodo secundario. Por eso son nodos de hoja. Por lo tanto, iniciaremos el método heapify desde su nodo principal. Estos son los pasos:
Paso 1) Seleccione el subárbol más a la izquierda. Si los nodos secundarios son mayores, intercambie el nodo principal por el nodo secundario.
Aquí el nodo padre es 9. Y los nodos secundarios son 17 y 60. Como 60 es el más grande, 60 y 9 se intercambiarán para mantener el montón máximo.
Paso 2) Ahora, el subárbol más a la izquierda está amontonado. El siguiente nodo principal es 7. Este padre tiene dos nodos secundarios y el más grande es 45. Por lo tanto, se intercambiarán 45 y 7.
Paso 3) Los nodos 60 y 4 tienen el nodo padre 5. Como "5" es más pequeño que el nodo hijo 60, se intercambiará.
Paso 4) Ahora, el nodo 5 tiene el nodo hijo 17,9. Esto no mantiene la propiedad del montón máximo. Entonces, 5 será reemplazado por 17.
Paso 5) El nodo 10 se intercambiará con el 60 y luego con el 17. El proceso se verá así:
Paso 6) Hasta el paso 5, creamos el montón máximo. Cada nodo padre es más grande que sus nodos hijos. El nodo raíz tiene el valor máximo (60).
Nota: Para crear la matriz ordenada, necesitamos reemplazar el nodo de valor máximo con su sucesor.
Este proceso se llama “extraer máximo”. Como 60 es el nodo máximo, fijaremos su posición en el índice 0 y crearemos el montón sin el nodo 60.
Paso 7) Como se elimina 60, el siguiente valor máximo es 45. Realizaremos el proceso "Extraer máximo" nuevamente desde el nodo 45.
Esta vez obtendremos 45 y reemplazaremos el nodo raíz con su sucesor 17.
Necesitamos actuar”Extraer máximo”Hasta que todos los elementos estén ordenados.
Luego de realizar estos pasos hasta extraer todos los valores máximos, obtendremos el siguiente array.
¿Qué es el montón binario?
Un montón binario es una especie de completo árbol binario estructura de datos. En este tipo de estructura de árbol, el nodo padre es mayor o menor que los nodos secundarios. Si el nodo principal es más pequeño, el montón se denomina "montón mínimo" y si el nodo principal es mayor, el montón se denomina "montón máximo".
A continuación se muestran ejemplos de montón mínimo y montón máximo.
En la figura anterior, si observa el "montón mínimo", el nodo principal siempre es más pequeño que sus nodos secundarios. En la cabecera del árbol podemos encontrar el valor más pequeño 10.
De manera similar, para el "Montón máximo", el nodo principal siempre es más grande que los nodos secundarios. El elemento máximo está presente en el nodo principal del "Max Heap".
¿Qué es “Heapify”?
“Heapify” es el principio del montón que asegura la posición del nodo. En Heapify, un montón máximo siempre mantiene una relación con el nodo padre y el nodo hijo, y es que el nodo padre será más grande que los nodos hijos.
Por ejemplo, si se agrega un nuevo nodo, debemos remodelar el montón. Sin embargo, es posible que debamos cambiar o intercambiar los nodos o reorganizar la matriz. Este proceso de remodelación de un montón se denomina "heapify".
Aquí hay un ejemplo de cómo funciona heapify:
Estos son los pasos para heapify:
Paso 1) Se agregó el nodo 65 como hijo derecho del nodo 60.
Paso 2) Compruebe si el nodo recién agregado es mayor que el padre.
Paso 3) Como es mayor que el nodo padre, intercambiamos el hijo derecho con su padre.
Cómo construir el montón
Antes de construir el montón o amontonar un árbol, necesitamos saber cómo lo almacenaremos. Como el montón es un árbol binario completo, es mejor usar un matriz para contener los datos del montón.
Digamos que una matriz contiene un total de n elementos. Si el índice "i" es un nodo principal, entonces el nodo izquierdo estará en el índice (2i+1), y el nodo derecho estará en el índice (2i+2). Suponemos que el índice de la matriz comienza desde 0.
Usando esto, almacenaremos un montón máximo en una matriz similar a la siguiente:
El algoritmo heapify mantiene la propiedad del montón. Si el padre no tiene el valor extremo (mayor o menor), se intercambiará con el nodo secundario más extremo.
Estos son los pasos para amontonar un montón máximo:
Paso 1) Comience desde el nodo hoja.
Paso 2) Encuentre el máximo entre padres e hijos.
Paso 3) Intercambie los nodos si el nodo secundario tiene un valor mayor que el principal.
Paso 4) Sube un nivel.
Paso 5) Siga los pasos 2,3,4 hasta llegar al índice 0 u ordenar todo el árbol.
Aquí está el pseudocódigo para heapify recursivo (montón máximo):
def heapify(): input→ array, size, i largest = i left = 2*i + 1 right = 2*i + 2 if left<n and array[largest ] < array[left]: largest = left if right<n and array[largest ] < array[right]: largest = right If largest not equals i: swap(array[i],array[largest]) heapify(array,n,largest)
Pseudocódigo para clasificación de montón
Aquí está el pseudocódigo para el algoritmo de clasificación del montón:
Heapify(numbers as an array, n as integer, i as integer): largest = i left = 2i+1 right= 2i+2 if(left<=n) and (numbers[i]<numbers[left]) largest=left if(right<=n) and (numbers[i]<numbers[right]) largest=right if(largest != i) swap(numbers[i], numbers[largest]) Heapify(numbers,n,largest) HeapSort(numbers as an array): n= numbers.size() for i in range n/2 to 1 Heapify(numbers,n,i) for i in range n to 2 Swap numbers[i] with numbers[1] Heapify(numbers,i,0)
Ejemplo de código de clasificación de montón en C++
#include <iostream>
using namespace std;
void display(int arr[], int n)
{
for (int i = 0; i < n; i++)
{
cout << arr[i] << "\t";
}
cout << endl;
}
void heapify(int numbers[], int n, int i)
{
int largest = i;
int left = 2 * i + 1;
int right = 2 * i + 2;
if (left < n && numbers[left] < numbers[largest])
{
largest = left;
}
if (right < n && numbers[right] < numbers[largest])
{
largest = right;
}
if (largest != i)
{
//uncomment the following line to see details in output
//cout<<"Swapping "<< numbers[i]<< " and "<<numbers[largest]<<endl;
swap(numbers[i], numbers[largest]);
heapify(numbers, n, largest);
}
}
void heapSort(int numbers[], int n)
{
for (int i = n/2 - 1; i >= 0; i--)
{
heapify(numbers, n, i);
//uncomment the following line to see details in output
//cout<<"Heapify:\t";
//display(numbers,n);
}
for (int i = n - 1; i >= 0; i--)
{
swap(numbers[0], numbers[i]);
heapify(numbers, i, 0);
}
}
int main()
{
int numbers[] = { 10,5, 7, 9, 4, 11, 45, 17, 60};
int size = sizeof(numbers) / sizeof(numbers[0]);
cout<<"Initial Array:\t";
display(numbers,size);
heapSort(numbers, size);
cout<<"Sorted Array (descending order):\t";
display(numbers, size);
}
Salida:
Initial Array: 10 5 7 9 4 11 45 17 60 Sorted Array (descending order): 60 45 17 11 10 9 7 5 4
Ejemplo de código de clasificación de montón en Python
def display(arr):
for i in range(len(arr)):
print(arr[i], end = "\t")
print()
def heapify(numbers, n, i):
largest = i
left = 2 * i + 1
right = 2 * i + 2
if left < n and numbers[left] < numbers[largest]:
largest = left
if right < n and numbers[right] < numbers[largest]:
largest = right
if largest != i:
numbers[i], numbers[largest] = numbers[largest], numbers[i]
heapify(numbers, n, largest)
def heapSort(items, n):
for i in range(n //2,-1,-1):
heapify(items, n, i) for i in range(n - 1, -1, -1):
items[0], items[i] = items[i], items[0] heapify(items, i, 0) numbers = [10, 5, 7, 9, 4, 11, 45, 17, 60] print("Initial List:\t", end = "") display(numbers) print("After HeapSort:\t", end = "") heapSort(numbers, len(numbers)) display(numbers)
Salida:
Initial List: 10 5 7 9 4 11 45 17 60 After HeapSort: 60 45 17 11 10 9 7 5 4
Análisis de complejidad temporal y espacial de Heap Sort
Existe una complejidad temporal y una complejidad espacial que podemos analizar para la ordenación por montículo. Para la complejidad temporal tenemos los siguientes casos:
- Mejores casos
- Caso promedio
- Peor de los casos
El montón se implementa en un árbol binario completo. Entonces, en el nivel inferior del árbol binario, estará el número máximo de nodos. Si el nivel inferior tiene n nodos, entonces el nivel superior tendrá n/2 nodos.
En este ejemplo, el nivel 3 tiene cuatro elementos, el nivel 2 tiene dos elementos y el nivel 1 tiene un elemento. Si hay un total de n elementos, la altura o nivel total será Registros2(norte). Por lo tanto, insertar un solo elemento podría requerir un máximo de iteraciones Log(n).
Cuando queremos tomar el valor máximo del montón, simplemente tomamos el nodo raíz. Luego, nuevamente, ejecutamos heapify. Cada heapify toma Registros2(norte) tiempo. Extraer el máximo lleva O(1) tiempo.
Mejora la complejidad temporal del caso para el algoritmo de ordenamiento por montículos
Cuando todos los elementos ya estén ordenados en la matriz, tomará O(n) tiempo construir el montón. Porque si la lista está ordenada, insertar un elemento tomará el tiempo constante que es O (1).
Por lo tanto, tomará O(n) tiempo crear un montón máximo o mínimo en el mejor de los casos.
Complejidad del tiempo promedio del caso para el algoritmo de ordenamiento por montículos
Insertar un elemento o extraer un máximo cuesta O(log(n)) tiempo. Por lo tanto, la complejidad temporal promedio del caso para el algoritmo de ordenamiento por montículo es O(n Iniciar sesión(n)).
Complejidad temporal en el peor de los casos para el algoritmo de ordenamiento por montículos
De manera similar al caso promedio, en el peor de los casos, podríamos realizar la operación de heapificación n veces. Cada operación de heapificación costará O(log(n)) tiempo. Por lo tanto, la complejidad temporal en el peor de los casos será O(n Iniciar sesión(n)).
Complejidad espacial para el algoritmo de ordenamiento de montículos
El ordenamiento por montículos es un algoritmo diseñado in situ. Esto significa que no se necesita memoria adicional o temporal para realizar la tarea. Si vemos la implementación, notaremos que usamos swap() para realizar el intercambio de nodos. No se necesitó ninguna otra lista o matriz. Por lo tanto, la complejidad espacial es O(1).
