Estructura de Datos Heap

En programación, una estructura de datos es una forma de organizar y almacenar datos en la memoria de una computadora para que se puedan acceder y utilizar de manera eficiente. Una de estas estructuras es el Heap, que es un tipo de árbol binario utilizado para organizar y recuperar elementos en orden de prioridad.

En este tutorial sobre la estructura de datos Heap, aprenderás qué es un Heap, cómo funciona, los diferentes tipos de Heap, operaciones básicas, su complejidad y cómo implementar un Heap en tu código.

📋 Aquí podrás encontrar✍

¿Qué es un Heap?
Operaciones básicas de un Heap
Complejidad
Cómo implementar un Heap
Ejemplos de código
Conclusión
Preguntas frecuentes

¿Qué es un Heap?

Un Heap es una estructura de datos de árbol binario completa, lo que significa que cada nivel está completamente lleno excepto potencialmente el último nivel, que se llena de izquierda a derecha. Además, un Heap cumple con la propiedad del Heap, lo que significa que la clave de cada padre en el árbol es menor o igual que la clave de los hijos.

Existen dos tipos de Heap: Max Heap y Min Heap. En un Max Heap, la clave de cada nodo es mayor o igual que la clave de sus hijos, mientras que en un Min Heap la clave de cada nodo es menor o igual que la clave de sus hijos.

Operaciones básicas de un Heap

Las operaciones básicas de un Heap son las siguientes:

Insertar: Se inserta un nuevo elemento en el Heap y se mantiene la propiedad del Heap.

Eliminar: Se elimina un elemento del Heap y se mantiene la propiedad del Heap.

Encontrar la raíz: Se obtiene el elemento de mayor o menor valor (dependiendo del tipo de Heap) en el Heap sin eliminarlo.

Complejidad

La complejidad de las operaciones en un Heap depende del tamaño del Heap y la estructura del árbol. La complejidad de las operaciones más comunes en un Heap son:

Insertar: O(log n)

Eliminar: O(log n)

Encontrar la raíz: O(1)

Donde n es el número de elementos en el Heap.

Cómo implementar un Heap

Un Heap se puede implementar utilizando un arreglo en lugar de un árbol. El primer elemento en el arreglo es la raíz del Heap y los demás elementos se van colocando en el orden que corresponde en el árbol.

Insertar: Para insertar un nuevo elemento en el Heap, se agrega al final del arreglo y se recorre hacia arriba para mantener la propiedad del Heap.

Eliminar: Para eliminar un elemento del Heap, se intercambia con el último elemento y luego se recorre hacia abajo para cumplir con la propiedad del Heap.

Ejemplos de código

Implementación de un Max Heap:

class MaxHeap: def __init__(self): self.heap = []


    def insert(self, value):

        self.heap.append(value)

        self.__floatUp(len(self.heap) - 1)
    def peek(self):

        if self.heap:

            return self.heap[0]

        else:

            return None
    def pop(self):

        if len(self.heap) > 1:

            self.__swap(0, len(self.heap) - 1)

            max = self.heap.pop()

            self.__bubbleDown(0)

        elif len(self.heap) == 1:

            max = self.heap.pop()

        else:

            max = None

        return max
    def __swap(self, i, j):

        self.heap[i], self.heap[j] = self.heap[j], self.heap[i]
    def __floatUp(self, index):

        parent = (index - 1) // 2

        if index <= 0:
            return
        elif self.heap[index] > self.heap[parent]:

            self.__swap(index, parent)

            self.__floatUp(parent)

def __bubbleDown(self, index): left = index * 2 + 1 right = index * 2 + 2 largest = index if len(self.heap) > left and self.heap[largest] < self.heap[left]: largest = left if len(self.heap) > right and self.heap[largest] < self.heap[right]: largest = right if largest != index: self.__swap(index, largest) self.__bubbleDown(largest)

Conclusión

El Heap es una estructura de datos útil para organizar y recuperar elementos en orden de prioridad. En este tutorial, aprendiste qué es un Heap, cómo funciona, los diferentes tipos de Heap, sus operaciones básicas, su complejidad y cómo implementar un Heap en tu código.