Estructura de datos de montón: ¿Qué es un montón?

¿Qué es una estructura de datos de montón?

Un montículo es una estructura de datos especializada basada en árboles. Esta estructura consta de un nodo superior llamado raíz (padre). Su segundo nodo es el hijo izquierdo de la raíz, mientras que el tercer nodo es el hijo derecho. Los nodos sucesivos se completan de izquierda a derecha. La clave del nodo padre se compara con la de sus descendientes para garantizar una correcta organización. El árbol es fácil de visualizar, ya que cada entidad se denomina nodo y cada nodo tiene una clave única para su identificación.

En términos sencillos, un montículo es un árbol binario completo que satisface la propiedad de montículo: cada padre está ordenado de forma consistente con respecto a sus hijos, lo que lo hace ideal para colas de prioridad y el algoritmo de ordenación por montículo (Heap Sort).

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

Estas son las principales razones para usar un Heap:

• La estructura de datos Heap permite la eliminación e inserción en tiempo logarítmico: O(log₂norte).
• Los datos en el árbol están organizados en un orden específico. Además de actualizar o consultar valores como el máximo o el mínimo, el programador puede encontrar relaciones entre el nodo padre y el nodo hijo.
• Puedes aplicar el concepto de Modelo de objeto de documento para ayudarte a comprender visualmente la estructura de datos Heap.
• Los montículos admiten operaciones eficientes de cola de prioridad, que son fundamentales para algoritmos de grafos como el de Dijkstra para encontrar la ruta más corta y el de Prim para encontrar el árbol de expansión mínima.

Tipos de montones

La estructura de datos de montón tiene varios algoritmos para manejar inserciones y eliminaciones de elementos, incluyendo cola de prioridad, montón binario, montón binomial y Ordenar montón.

• Cola de prioridad: Es un abstracEstructura de datos que contiene objetos priorizados. Cada objeto o elemento tiene una prioridad preestablecida. Por lo tanto, el objeto o elemento con mayor prioridad recibe el servicio antes que los demás.
• Montón binario: Los montículos binarios son adecuados para operaciones sencillas como eliminaciones e inserciones. Son la implementación predeterminada de la mayoría de las colas de prioridad de las bibliotecas estándar.
• Montículo binomial: Un montículo binomial consta de una serie de colecciones de árboles binomiales que conforman el montículo. Un árbol de montículo binomial no es un árbol ordinario, ya que está definido rigurosamente. El número total de elementos en un árbol binomial siempre es igual a 2.ⁿ nodos
• Ordenación por montículo: A diferencia de la mayoría de los algoritmos de ordenación, Heap Sort utiliza un espacio de O(1) para su operación de ordenación. Es un algoritmo de ordenación basado en comparaciones, donde la ordenación se realiza en orden ascendente, transformando primero la entrada en un Max-Heap. Heap Sort puede considerarse una versión mejorada del árbol de búsqueda binaria.

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

• Montón mínimo – menor valor en la parte superior
• Montón máximo – 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 el de sus hijos. Por lo tanto, la raíz de un Min-Heap contiene el valor mínimo. El Min-Heap es también un árbol binario completo.

Una vez que se tiene un Min-Heap en un árbol, todas las hojas son candidatas viables para el valor máximo. Sin embargo, es necesario examinar cada hoja para obtener el valor exacto del Max-Heap.

Ejemplo de montículo mínimo

En el diagrama anterior, se puede observar una secuencia clara desde la raíz hasta el nodo más bajo.

Supongamos que almacenamos los elementos en el array Array_N[12, 2, 8, 1, 4]. Como se puede observar, el elemento raíz infringe la prioridad de Min-Heap. Para mantener la propiedad de Min-Heap, debemos realizar operaciones de min-heapify para intercambiar los elementos hasta que se cumplan las reglas de Min-Heap.

Montón máximo

En la estructura Max-Heap, el nodo padre o raíz tiene un valor igual o mayor que el de sus hijos. Este nodo almacena el valor máximo. Se trata de un árbol binario completo, por lo que se puede construir un Max-Heap a partir de una colección de valores en tiempo O(n).

Aquí hay algunos métodos comúnmente utilizados al implementar un Java Montón máximo:

• Agregar (): Coloca un nuevo elemento en un montón. Si se utiliza un array, los objetos se añaden al final del mismo, mientras que en un árbol binario, los objetos se añaden de arriba abajo y luego de izquierda a derecha.
• Eliminar (): Este método permite eliminar el primer elemento de la lista de arreglos. Como el elemento recién ascendido ya no es el más grande, el método Sift-Down siempre lo mueve a su nueva posición.
• Redondeo descendente (): Este método compara un objeto raíz con sus objetos hijos y luego mueve el nodo reubicado a su posición correcta.
• Cifrado ascendente (): Si se utiliza el método de matriz para agregar un elemento recién insertado a una matriz, el método Sift-Up ayuda a que el nodo recién agregado se reubique en su posición correcta. El nuevo elemento se compara primero con su padre simulando la estructura de datos del árbol.

  Aplica la fórmula Índice_Padre = Índice_Hijo / 2. Continúa haciendo esto hasta que el elemento máximo esté al principio de la matriz.

Montón básico OperaSupuestos de Alcance

Para encontrar los valores más altos y más bajos en un conjunto de datos, necesitas algunas operaciones básicas de montículo, como buscar, insertar y eliminar. Dado que los elementos aparecen y desaparecen constantemente, debes saber cómo:

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

crear montones

El proceso de construcción de montones se conoce como creación de montones. A partir de una lista de claves, el programador crea un montón vacío y luego inserta las demás claves una a una utilizando las operaciones básicas de los montones.

Así pues, comencemos a construir un Min-Heap utilizando el método de William insertando los valores 12, 2, 8, 1 y 4. Puedes construir el heap con n elementos comenzando con un heap vacío y luego llenándolo sucesivamente con otros elementos en un tiempo de O(n log n).

• Amontonar: Una rutina de inserción que ayuda a insertar elementos en un montón preservando la propiedad de montón.

  Por ejemplo, una operación max-heapify comprueba que el valor del padre sea mayor que el de su descendiente. Los elementos se pueden ordenar utilizando métodos como swap.ping.

• Unir: Cuando tengas dos montones que quieras combinar en uno solo, usa la operación de fusión para unir los valores de ambos montones. Los montones originales se conservan.

Inspeccionar montones

La inspección de montones consiste en comprobar el número de elementos en la estructura de datos del montón y validar si el montón está vacío.

Es importante inspeccionar los montículos al ordenar o poner en cola elementos. Es fundamental verificar que haya elementos para procesar usando IsEmpty(). El tamaño del montículo ayudará a localizar las raíces del montículo máximo o mínimo, por lo que es necesario saber cuántos elementos siguen la propiedad del montículo.

• Tamaño – Devuelve la magnitud o longitud del montón. Indica cuántos elementos están almacenados en orden ascendente.
• Está-Vacío – devuelve VERDADERO si el montón es nulo, 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 de montón es útil en muchas aplicaciones de programación en la vida real, tales como:

• Ayuda a filtrar el correo no deseado.
• Implementación de algoritmos de grafos como Dijkstra y Prim.
• OperaBalanceo de carga del sistema y compresión de datos.
• Hallar estadísticas de orden, como el k-ésimo elemento más pequeño.
• Implementar colas de prioridad donde se pueden buscar elementos en una lista en tiempo logarítmico.
• La estructura de datos de montón también se utiliza para ordenar mediante el algoritmo de ordenación por montón (Heap Sort).
• Simulando clientes en una fila de espera.
• Manejo de interrupciones en el Operating sistema.
• En la codificación Huffman para la compresión de datos.
• Impulsando la búsqueda primero el mejor y las heurísticas A* en la planificación de rutas de IA.

Propiedades de la cola de prioridad del montón

Las siguientes propiedades describen cómo se comporta la cola de prioridad construida sobre un montón:

• En los montículos de prioridad, los elementos de datos de la lista se comparan entre sí para determinar cuál es el más pequeño o el más grande.
• Un elemento se coloca en una cola y posteriormente se elimina en orden de prioridad.
• Cada elemento de la cola de prioridad tiene un número único asociado que lo identifica como una prioridad.
• Al salir de una cola de prioridad, el elemento de máxima prioridad sale primero.

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

La siguiente sección se adentra en un terreno concreto. Java Implementación que convierte estas reglas en código funcional.

Ordenar en montón Java con Code Ejemplo

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 and heapify the sub-tree
        if (largest != i) {
            int temp = arr[i];
            arr[i] = arr[largest];
            arr[largest] = temp;
            heapify(arr, n, largest);
        }
    }
}

Resultado

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 Code 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)

Resultado

[1, 3, 4, 7, 9]

A continuación, aprenderás sobre el Método de bisección.

Preguntas Frecuentes