Implementar Min Heap en Python

1. El montón mínimo en Python
2. Crear una clase para implementar Min Heap en Python
3. Use el módulo heapq para implementar Min Heap en Python

Los árboles son una estructura de datos no lineal donde los elementos se organizan en múltiples niveles. Heap es una estructura de datos basada en árboles.

Es un árbol binario completo, lo que significa que cada nodo principal tiene dos nodos secundarios. Los montones implementan diferentes algoritmos, ordenan otras estructuras, priorizan colas, etc.

Los montones son de dos tipos: máximo y mínimo. Estos se basan en el valor del nodo secundario en comparación con el nodo principal.

Este tutorial analizará Min Heap y su implementación en Python.

El montón mínimo en Python

Cada nodo principal es menor o igual que el nodo secundario en un montón mínimo. Sigue el orden ascendente, y la prioridad siempre es con el nodo más pequeño.

Para un nodo dado n, su hijo izquierdo estará en 2n+1 y el derecho en 2n+2.

Vea la siguiente imagen.

En Python, Min Heap se puede implementar de dos maneras. Estos se discuten a continuación.

Crear una clase para implementar Min Heap en Python

Podemos crear una clase para implementar Min Heap en Python. Iniciaremos el objeto de clase con el tamaño del heap y definiremos métodos para realizar el proceso de inserción de elementos y mapearlos a sus respectivos índices.

Ejemplo:

import sys


class min_heap:
    def __init__(self, size):
        self.storage = [0] * size
        self.size = size
        self.heap_size = 0
        self.Heap = [0] * (self.size + 1)
        self.Heap[0] = sys.maxsize * -1
        self.parent = 1
        self.root = 1

    def parent_idx(self, idx):
        return (idx - 1) // 2

    def lf_child_idx(self, idx):
        return 2 * idx + 1

    def rt_child_idx(self, idx):
        return 2 * idx + 2

    def has_parent(self, idx):
        return self.parent_idx(idx) >= 0

    def insert(self, idx):
        if self.heap_size >= self.size:
            return
        self.heap_size += 1
        self.Heap[self.heap_size] = idx
        heap = self.heap_size
        while self.Heap[heap] < self.Heap[heap // 2]:
            self.swap(heap, heap // 2)
            heap = heap // 2

    def swap(self, left, right):
        self.Heap[left], self.Heap[right] = self.Heap[right], self.Heap[left]

    def print_heap(self):
        for i in range(1, (self.heap_size // 2) + 1):
            print(
                "Parent:",
                str(self.Heap[i]),
                "Lt: " + str(self.Heap[2 * i]),
                "Rt: ",
                str(self.Heap[2 * i + 1]),
            )


min_heap = min_heap(10)
min_heap.insert(5)
min_heap.insert(1)
min_heap.insert(8)
min_heap.insert(2)
min_heap.insert(3)
min_heap.insert(7)
min_heap.insert(9)
min_heap.insert(6)
min_heap.insert(10)
min_heap.print_heap()

Producción :

Parent: 1 Lt: 2 Rt:  7
Parent: 2 Lt: 5 Rt:  3
Parent: 7 Lt: 8 Rt:  9
Parent: 5 Lt: 6 Rt:  10

El método insert() agrega elementos al montón. El índice y el orden de los elementos se gestionan mediante el método swap() que utiliza las funciones rt_child_index() y lt_child_index() para ajustar los niveles de los nodos secundarios en función del valor de los nodos principales.

El Min Heap se itera y se muestra en una secuencia usando la función print_heap() de la clase.

Use el módulo heapq para implementar Min Heap en Python

Python proporciona un módulo heapq que puede implementar la estructura de datos del montón sin crear otras clases. Este módulo garantiza que el elemento más pequeño del montón se saque cada vez para mantener la estructura del montón mínimo.

Usaremos una lista para mantener los nodos del montón. Los elementos se agregan usando la función heappush(), y mantiene el orden en consecuencia para que se mantenga la estructura de Min Heap.

El heappop() extrae el elemento más pequeño del montón, el nodo raíz.

Ejemplo:

import heapq as heap

lst = []
heap.heappush(lst, 7)
heap.heappush(lst, 1)
heap.heappush(lst, 5)
heap.heappush(lst, 4)
heap.heappush(lst, 8)
heap.heappush(lst, 3)
print("Heap: ", lst)
print("Parent Node: ", heap.heappop(lst))
print("Child Nodes: ", lst)

Producción :

Heap:  [1, 4, 3, 7, 8, 5]
Parent Node:  1
Child Nodes:  [3, 4, 5, 7, 8]

En el ejemplo anterior, usamos una lista lst para mantener el montón. Los elementos se añaden y su orden se ajusta automáticamente con la función heappush().

Se muestra el montón mínimo. El nodo principal se extrae utilizando el método heappop() y se muestra.

Los nodos secundarios restantes también se muestran después de eliminar el nodo principal.