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:
- getMin() : Devuelve el elemento raíz de Min Heap. La complejidad temporal de esta operación es O(1) .
- 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.
- 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
# 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
# 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
Publicación traducida automáticamente
Artículo escrito por chaudhary_19 y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA