Estructura de datos del montón: ¿Qué es el montón? Montón mínimo y máximo (ejemplo)

¿Qué es un montón?

El montón es una estructura de datos especializada en forma de árbol. El montón comprende el nodo superior, llamado raíz (padre). Su segundo hijo es el hijo izquierdo de la raíz, mientras que el tercer nodo es el hijo derecho de la raíz. Los nodos sucesivos se llenan de izquierda a derecha. La clave del nodo padre se compara con la de su descendencia y se produce una disposición adecuada. El árbol es fácil de visualizar, ya que cada entidad se denomina nodo. El nodo tiene claves únicas para su identificación.

¿Por qué necesita una estructura de datos de montón?

Estas son las razones principales para utilizar la estructura de datos del montón:

La estructura de datos del montón permite la eliminación e inserción en tiempo logarítmico – O(log₂norte).
Los datos del árbol se forman en un orden particular. Además de actualizar o consultar cosas como un máximo o un mínimo, el programador puede encontrar relaciones entre el padre y la descendencia.
Puedes aplicar el concepto de Modelo de objeto de documento para ayudarle a comprender la estructura de datos del montón.

Tipos de montones

La estructura de datos del montón tiene varios algoritmos para manejar inserciones y eliminar elementos en una estructura de datos del montón, incluidos Priority-Queue, Binary-Heap, Binomial Heap y Ordenación de montón.

Cola de prioridad: Es una estructura de datos abstracta que contiene objetos priorizados. Cada objeto o artículo tiene una prioridad preestablecida para él. Por lo tanto, el objeto o elemento al que se le asigna mayor prioridad es el que recibe el servicio antes que el resto.
Montón binario: Los montones binarios son adecuados para operaciones de montón simples, como eliminaciones e inserciones.
Montón binomial: Un montón binomial consta de una serie de colecciones de árboles binomiales que forman el montón. El árbol Binomial Heap no es un árbol ordinario, ya que está rigurosamente definido. El número total de elementos en un árbol binomial siempre posee 2ⁿ nodos
Clasificación de montón: A diferencia de la mayoría de los algoritmos de clasificación, la clasificación en montón utiliza el espacio O(1) para su operación de clasificación. Es un algoritmo de clasificación basado en comparaciones en el que la clasificación se produce en orden creciente convirtiéndolo primero en un montón máximo. Puede considerar Heapsort como un árbol de búsqueda binaria de calidad mejorada.

Normalmente, una estructura de datos de montón emplea dos estrategias. Para entrada 12 – 8 – 4 – 2 y 1

Montón mínimo: valor mínimo en la parte superior
Max Heap: valor más alto en la parte superior

Montón mínimo

En la estructura Min Heap, el nodo raíz tiene un valor igual o menor que los hijos de ese nodo. Este nodo de montón de un montón mínimo tiene el valor mínimo. Con todo, su estructura min-heap es completa árbol binario.

Una vez que tienes un montón mínimo en un árbol, todas las hojas son candidatas viables. Sin embargo, es necesario examinar cada una de las hojas para obtener el valor máximo exacto del montón.

Ejemplo de montón mínimo

En los diagramas anteriores, puede observar una secuencia clara desde la raíz hasta el nodo más bajo.

Supongamos que almacena los elementos en la matriz Array_N[12,2,8,1,4]. Como puede ver en la matriz, el elemento raíz viola la prioridad de Min Heap. Para mantener la propiedad de Min Heap, debe realizar las operaciones de min-heapify para intercambiar los elementos hasta que se cumplan las propiedades de Min Heap.

Montón máximo

En la estructura de Max Heap, el nodo principal o raíz tiene un valor igual o mayor que sus hijos en el nodo. Este nodo tiene el valor máximo. Además, es un árbol binario completo, por lo que puedes crear un montón máximo a partir de una colección de valores y ejecutarlo en tiempo O(n).

A continuación se muestran algunos métodos para implementar un montón máximo de Java.

Agregar (): coloca un nuevo elemento en un montón. Si usa una matriz, los objetos se agregan al final de la matriz, mientras que en el árbol binario, los objetos se agregan de arriba a abajo y luego de izquierda a derecha.
Eliminar (): Este método le permite eliminar el primer elemento de la lista de matrices. Como el elemento recién agregado ya no es el más grande, el método Sift-Down siempre lo empuja a su nueva ubicación.
Tamizar ():Este método compara un objeto raíz con su hijo y luego empuja el nodo recién agregado a su posición correcta.
Tamizar (): si utiliza el método de matriz para agregar un elemento recién insertado a una matriz, entonces el método Sift-Up ayuda al nodo recién agregado a reubicarse en su nueva posición. El elemento recién insertado se compara primero con el elemento principal simulando la estructura de datos del árbol.
Aplicar la fórmula Parent_Index=Child_Index/2. Continúa haciendo esto hasta que el elemento máximo esté al frente de la matriz.

Montón básico OperaSupuestos de Alcance

Para encontrar los valores más alto y más bajo en un conjunto de datos, necesita muchas operaciones básicas del montón, como buscar, eliminar e insertar. Debido a que los elementos van y vienen constantemente, debes:

Encuentre – Busca un artículo en un montón.
recuadro – Agrega un nuevo niño al montón.
Borrar – Eliminar un nodo de un montón.

crear montones

El proceso de construir montones se conoce como creación de montones. Dada una lista de claves, el programador crea un montón vacío y luego inserta otras claves una a la vez utilizando operaciones básicas de montón.

Entonces, comencemos a construir un montón mínimo usando el método de Willaim insertando los valores 12,2,8,1 y 4 en un montón. Puede construir el montón con n elementos comenzando con un montón vacío y luego llenándolo sucesivamente con otros elementos usando el tiempo O (nlogn).

Heapify: algoritmo de inserción que ayuda a insertar elementos en un montón. Comprueba si se respetan las propiedades de la estructura de datos del montón resaltadas.
Por ejemplo, una función de heapificación máxima comprobaría si el valor del elemento principal es mayor que el de su elemento secundario. Los elementos se pueden ordenar mediante métodos como el intercambio.

Fusionar: teniendo en cuenta que tiene dos montones para combinar en uno, utilice montones de combinación para unir los valores de los dos montones. Sin embargo, aún se conservan los montones originales.

Inspeccionar montones

Inspeccionar montones se refiere a verificar la cantidad de elementos en la estructura de datos del montón y validar si el montón está vacío.

Es importante inspeccionar los montones como método de clasificación o de puesta en cola de elementos. Es importante comprobar si hay elementos para procesar mediante Is-Empty(). El tamaño del montón ayudará a localizar el montón máximo o mínimo. Por lo tanto, es necesario conocer los elementos que siguen a la propiedad del montón.

Tamaño – devuelve la magnitud o longitud del montón. Puedes saber cuántos elementos hay en orden.
Esta vacio – si el montón es NULL, devuelve VERDADERO; de lo contrario, devuelve FALSO.

Aquí, estás imprimiendo todos los elementos en el prioridadQ bucle y luego comprobar que la prioridadQ no esté vacía.

//print head the head values
       While (!priorityQ.isEmpty()) {
        System.out.print(priorityQ.poll()+" ");

Usos de la estructura de datos del montón

La estructura de datos del montón es útil en muchas aplicaciones de programación en la vida real, como:

Ayuda en el filtrado de spam.
Implementación de algoritmos de gráficos.
OperaEquilibrio de carga del sistema y compresión de datos.
Encuentra el orden en las estadísticas.
Implemente colas de prioridad donde pueda buscar elementos en una lista en tiempo logarítmico.
La estructura de datos del montón también se utiliza para ordenar.
Simulando clientes en una línea.
Interrumpir el manejo en Operating sistema.
En la codificación de Huffman para la compresión de datos.

Propiedades de la cola de prioridad del montón

En los montones de prioridad, los elementos de datos de la lista se comparan entre sí para determinar el elemento más pequeño.
Un elemento se coloca en una cola y luego se elimina.
Cada elemento de la cola de prioridades tiene un número único relacionado con él identificado como prioridad.
Al salir de una cola de prioridad, el elemento de mayor prioridad sale primero.

Pasos para implementar la cola de prioridad del montón en Java

Ordenación de montón en JAVA con ejemplo de código

import java.util.Arrays;
public class HeapSort {
    public static void main(String[] args) {
        int[] arr = {5, 9, 3, 1, 8, 6};
        // Sort the array using heap sort
        heapSort(arr);
        // Print the sorted array
        System.out.println(Arrays.toString(arr));
    }
    public static void heapSort(int[] arr) {
        // Convert the array into a heap
        for (int i = arr.length / 2 - 1; i >= 0; i--) {
            heapify(arr, arr.length, i);
        }
        // Extract the maximum element from the heap and place it at the end of the array
        for (int i = arr.length - 1; i >= 0; i--) {
            int temp = arr[0];
            arr[0] = arr[i];
            arr[i] = temp;
            heapify(arr, i, 0);
        }
    }
    public static void heapify(int[] arr, int n, int i) {
        int largest = i;
        int left = 2 * i + 1;
        int right = 2 * i + 2;
        // Find the largest element among the root, left child, and right child
        if (left < n && arr[left] > arr[largest]) {
            largest = left;
        }
        if (right < n && arr[right] > arr[largest]) {
            largest = right;
        }
        // If the largest element is not the root, swap the root and the largest element and heapify the sub-tree
        if (largest != i) {
            int temp = arr[i];
            arr[i] = arr[largest];
            arr[largest] = temp;
            heapify(arr, n, largest);
        }
    }
}

Salida

Original Array:

5 9 3 1 8 6

Heap after insertion:

9 8 6 1 5 3

Heap after sorting:

1 3 5 6 8 9

Ordenar en montón Python con código de ejemplo

def heap_sort(arr):
    """
    Sorts an array in ascending order using heap sort algorithm.
    Parameters:
        arr (list): The array to be sorted.
    Returns:
        list: The sorted array.
    """
    n = len(arr)
    # Build a max heap from the array
    for i in range(n // 2 - 1, -1, -1):
        heapify(arr, n, i)
    # Extract elements from the heap one by one
    for i in range(n - 1, 0, -1):
        arr[0], arr[i] = arr[i], arr[0]  # swap the root with the last element
        heapify(arr, i, 0)  # heapify the reduced heap
    return arr
def heapify(arr, n, i):
    """
    Heapifies a subtree with the root at index i in the given array.
    Parameters:
        arr (list): The array containing the subtree to be heapified.
        n (int): The size of the subtree.
        i (int): The root index of the subtree.
    """
    largest = i  # initialize largest as the root
    left = 2 * i + 1  # left child index
    right = 2 * i + 2  # right child index
    # If left child is larger than root
    if left < n and arr[left] > arr[largest]:
        largest = left
    # If right child is larger than largest so far
    if right < n and arr[right] > arr[largest]:
        largest = right
    # If largest is not root
    if largest != i:
        arr[i], arr[largest] = (
            arr[largest],
            arr[i],
        )  # swap the root with the largest element
        heapify(arr, n, largest)  # recursively heapify the affected subtree
arr = [4, 1, 3, 9, 7]
sorted_arr = heap_sort(arr)
print(sorted_arr)