Montón mínimo en Python

Un Min-Heap es un árbol binario completo en el que el valor de cada Node interno es menor o igual que los valores de los elementos secundarios de ese Node. 
Mapear los elementos de un montón en una array es trivial: si un Node se almacena en el índice k , entonces su hijo izquierdo se almacena en el índice 2k + 1 y su hijo derecho en el índice 2k + 2 para la indexación basada en 0 y para la indexación basada en 1 el niño izquierdo estará en 2k y el niño derecho estará en 2k + 1 .

Ejemplo de montón mínimo:  

            5                      13
          /   \                  /    \  
        10     15              16      31 
       /                      /  \     /  \
     30                     41    51  100  41

¿Cómo se representa Min Heap?  
Un montón mínimo es un árbol binario completo. Un montón mínimo normalmente se representa como una array. El elemento raíz estará en Arr[0] . Para cualquier i-ésimo Node, es decir, Arr[i] :

• Arr[(i -1) / 2] devuelve su Node principal.
• Arr[(2 * i) + 1] devuelve su Node secundario izquierdo.
• Arr[(2 * i) + 2] devuelve su Node secundario derecho.

Operaciones en Min Heap: 

1. getMin() : Devuelve el elemento raíz de Min Heap. La complejidad temporal de esta operación es O(1) .
2. extractMin() : elimina el elemento mínimo de MinHeap. La complejidad de tiempo de esta operación es O (Log n) ya que esta operación necesita mantener la propiedad del montón (llamando a heapify()) después de eliminar la raíz.
3. insert() : Insertar una nueva clave lleva tiempo O (Iniciar sesión) . Agregamos una nueva clave al final del árbol. Si la nueva clave es más grande que su padre, entonces no necesitamos hacer nada. De lo contrario, debemos recorrer hacia arriba para corregir la propiedad del montón violada.

A continuación se muestra la implementación de Min Heap en Python: 

# Python3 implementation of Min Heap
  
import sys
  
class MinHeap:
  
    def __init__(self, maxsize):
        self.maxsize = maxsize
        self.size = 0
        self.Heap = [0]*(self.maxsize + 1)
        self.Heap[0] = -1 * sys.maxsize
        self.FRONT = 1
  
    # Function to return the position of
    # parent for the node currently
    # at pos
    def parent(self, pos):
        return pos//2
  
    # Function to return the position of
    # the left child for the node currently
    # at pos
    def leftChild(self, pos):
        return 2 * pos
  
    # Function to return the position of
    # the right child for the node currently
    # at pos
    def rightChild(self, pos):
        return (2 * pos) + 1
  
    # Function that returns true if the passed
    # node is a leaf node
    def isLeaf(self, pos):
        return pos*2 > self.size
  
    # Function to swap two nodes of the heap
    def swap(self, fpos, spos):
        self.Heap[fpos], self.Heap[spos] = self.Heap[spos], self.Heap[fpos]
  
    # Function to heapify the node at pos
    def minHeapify(self, pos):
  
        # If the node is a non-leaf node and greater
        # than any of its child
        if not self.isLeaf(pos):
            if (self.Heap[pos] > self.Heap[self.leftChild(pos)] or 
               self.Heap[pos] > self.Heap[self.rightChild(pos)]):
  
                # Swap with the left child and heapify
                # the left child
                if self.Heap[self.leftChild(pos)] < self.Heap[self.rightChild(pos)]:
                    self.swap(pos, self.leftChild(pos))
                    self.minHeapify(self.leftChild(pos))
  
                # Swap with the right child and heapify
                # the right child
                else:
                    self.swap(pos, self.rightChild(pos))
                    self.minHeapify(self.rightChild(pos))
  
    # Function to insert a node into the heap
    def insert(self, element):
        if self.size >= self.maxsize :
            return
        self.size+= 1
        self.Heap[self.size] = element
  
        current = self.size
  
        while self.Heap[current] < self.Heap[self.parent(current)]:
            self.swap(current, self.parent(current))
            current = self.parent(current)
  
    # Function to print the contents of the heap
    def Print(self):
        for i in range(1, (self.size//2)+1):
            print(" PARENT : "+ str(self.Heap[i])+" LEFT CHILD : "+ 
                                str(self.Heap[2 * i])+" RIGHT CHILD : "+
                                str(self.Heap[2 * i + 1]))
  
    # Function to build the min heap using
    # the minHeapify function
    def minHeap(self):
  
        for pos in range(self.size//2, 0, -1):
            self.minHeapify(pos)
  
    # Function to remove and return the minimum
    # element from the heap
    def remove(self):
  
        popped = self.Heap[self.FRONT]
        self.Heap[self.FRONT] = self.Heap[self.size]
        self.size-= 1
        self.minHeapify(self.FRONT)
        return popped
  
# Driver Code
if __name__ == "__main__":
      
    print('The minHeap is ')
    minHeap = MinHeap(15)
    minHeap.insert(5)
    minHeap.insert(3)
    minHeap.insert(17)
    minHeap.insert(10)
    minHeap.insert(84)
    minHeap.insert(19)
    minHeap.insert(6)
    minHeap.insert(22)
    minHeap.insert(9)
    minHeap.minHeap()
  
    minHeap.Print()
    print("The Min val is " + str(minHeap.remove()))

Producción : 

The Min Heap is 
 PARENT : 3 LEFT CHILD : 5 RIGHT CHILD :6
 PARENT : 5 LEFT CHILD : 9 RIGHT CHILD :84
 PARENT : 6 LEFT CHILD : 19 RIGHT CHILD :17
 PARENT : 9 LEFT CHILD : 22 RIGHT CHILD :10
The Min val is 3

Uso de funciones de biblioteca:
usamos la clase heapq para implementar Heaps en Python. Esta clase implementa Min Heap de forma predeterminada.  

# Python3 program to demonstrate working of heapq
  
from heapq import heapify, heappush, heappop
  
# Creating empty heap
heap = []
heapify(heap)
  
# Adding items to the heap using heappush function
heappush(heap, 10)
heappush(heap, 30)
heappush(heap, 20)
heappush(heap, 400)
  
# printing the value of minimum element
print("Head value of heap : "+str(heap[0]))
  
# printing the elements of the heap
print("The heap elements : ")
for i in heap:
    print(i, end = ' ')
print("\n")
  
element = heappop(heap)
  
# printing the elements of the heap
print("The heap elements : ")
for i in heap:
    print(i, end = ' ')

Producción :  

Head value of heap : 10
The heap elements : 
10 30 20 400 

The heap elements : 
20 30 400