Algoritmo de clasificación de montón (con código en Python y C++)

¿Qué es el algoritmo de clasificación de montón?

Heap Sort es uno de los algoritmos de clasificación más populares y más rápidos. Está construido sobre la estructura de datos completa del árbol binario. Buscaremos el elemento máximo y lo colocaremos en la parte superior del montón máximo. Lo colocaremos en el nodo padre 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í:

Algoritmo de clasificación de montón

Haremos el proceso de apilamiento desde el principio hasta el final de la matriz. Inicialmente, si convertimos la matriz en un árbol, se verá como el anterior. Podemos ver que no mantiene ninguna propiedad del montón (montón mínimo o montón máximo). Obtendremos la matriz ordenada realizando el proceso de acumulació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 O (1) espacio complexity.

Crear clasificación de montón con ejemplo

Aquí, construiremos un montón máximo a partir de lo siguiente.wing árbol binario completo.

Crear clasificación de montón con ejemplo

Los nodos hoja son 17, 60, 4, 11 y 45. No tienen nodos secundarios. Por eso son nodos hoja. Entonces, iniciaremos el método heapify desde su nodo principal. Aquí están 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.

Crear clasificación de montón con ejemplo

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.

Crear clasificación de montón con ejemplo

Crear clasificación de montón con ejemplo

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á.

Crear clasificación de montón con ejemplo

Crear clasificación de montón con ejemplo

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.

Crear clasificación de montón con ejemplo

Paso 5) El nodo 10 se intercambiará con el 60 y luego con el 17. El proceso se verá asíwing.

Crear clasificación de montón con ejemplo

Crear clasificación de montón con ejemplo

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.

Crear clasificación de montón con ejemplo

Crear clasificación de montón con ejemplo

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.

Después de realizar estos pasos hasta que extraigamos todos los valores máximos, obtendremos lo siguientewing formación.

Crear clasificación de montón con ejemplo

¿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.

Montón mínimo y montón máximo
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 padre y el hijo, y es decir, el nodo padre será más grande que los nodos secundarios.

Por ejemplo, si se agrega un nuevo nodo, debemos remodelar el montón. Sin embargo, es posible que necesitemos cambiar o intercambiar los nodos o reorganizar la matriz. Este proceso de remodelación de un montón se llama "heapify".

Aquí hay un ejemplo de cómo funciona heapify:

Agregar un nuevo nodo y Heapify
Agregar un nuevo nodo y apilar

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 apilar 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, almacenemos un montón máximo en un seguimiento similar a una matriz.wing:

Representación basada en matrices del Max Heap
Representación basada en matrices del montón máximo

El algoritmo heapify mantiene la propiedad del montón. Si el padre no tiene el valor extremo (menor o mayor), se intercambiará con el nodo hijo más extremo.

Estos son los pasos para acumular 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

Tiempo y Espacio Complexanálisis de calidad de Heap Sort

Hay tiempo complexciudad y espacio complexidad que podemos analizar para el tipo de montón. por tiempo complexity tenemos el siguientewing casos:

  1. Mejor caso
  2. Caso promedio
  3. 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.

Tiempo y Espacio ComplexAnálisis de idad

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á Log2(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. Por otra parte, ejecute heapify. Cada montón toma Log2(norte) tiempo. Extraer el máximo lleva O(1) tiempo.

Mejor caso tiempo complexidad para el algoritmo de clasificación de montón

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.

Tiempo promedio de caso Complexidad para el algoritmo de clasificación de montón

Insertar un artículo o extraer un máximo cuesta O(log(n)) tiempo. Entonces, el tiempo promedio de caso complexLa calidad del algoritmo de clasificación del montón es O(n Iniciar sesión(n)).

Peor caso de tiempo Complexidad para el algoritmo de clasificación de montón

De manera similar al caso promedio, en el peor de los casos, podríamos realizar heapify n veces. Cada montón costará O (log (n)) tiempo. Entonces, el peor de los casosplexla ciudad será O(n Iniciar sesión(n)).

Espacio Complexidad para el algoritmo de clasificación de montón

La clasificación de montón 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 los nodos. No se necesitaba ninguna otra lista o matriz. Entonces, la comunicación espacialplexLa ciudad es O(1).