Ein Min-Heap ist ein vollständiger Binärbaum, in dem der Wert in jedem internen Knoten kleiner oder gleich den Werten in den untergeordneten Knoten dieses Knotens ist. 
Das Zuordnen der Elemente eines Heaps zu einem Array ist trivial: Wenn ein Knoten im Index k gespeichert ist, wird sein linkes Kind im Index 2k + 1 und sein rechtes Kind im Index 2k + 2 gespeichert .

Beispiel für Min Heap:  

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

Wie ist Min Heap dargestellt?  
Ein Min Heap ist ein vollständiger Binärbaum. Ein Min-Heap wird normalerweise als Array dargestellt. Das Wurzelelement befindet sich bei Arr [0] . Für jeden i-ten Knoten, dh Arr [i] :

• Arr [(i -1) / 2] gibt seinen übergeordneten Knoten zurück.
• Arr [(2 * i) + 1] gibt seinen linken untergeordneten Knoten zurück.
• Arr [(2 * i) + 2] gibt seinen rechten untergeordneten Knoten zurück.

Operationen auf Min Heap: 

1. getMin() : Gibt das Stammelement von Min Heap zurück. Die zeitliche Komplexität dieser Operation ist O (1) .
2. extractMin() : Entfernt das minimale Element aus MinHeap. Die zeitliche Komplexität dieser Operation ist O (Log n), da diese Operation die Heap-Eigenschaft (durch Aufrufen von heapify()) nach dem Entfernen von root beibehalten muss.
3. insert() : Das Einfügen eines neuen Schlüssels dauert O (Log n) . Wir fügen am Ende des Baums einen neuen Schlüssel hinzu. Wenn der neue Schlüssel größer als der übergeordnete ist, müssen wir nichts tun. Andernfalls müssen wir nach oben gehen, um die verletzte Heap-Eigenschaft zu beheben.

Unten ist die Implementierung von Min Heap in Python - 

 
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
 
    
    
    
    def parent(self, pos):
        return pos//2
 
    
    
    
    def leftChild(self, pos):
        return 2 * pos
 
    
    
    
    def rightChild(self, pos):
        return (2 * pos) + 1
 
    
    
    def isLeaf(self, pos):
        if pos >= (self.size//2) and pos <= self.size:
            return True
        return False
 
    
    def swap(self, fpos, spos):
        self.Heap[fpos], self.Heap[spos] = self.Heap[spos], self.Heap[fpos]
 
    
    def minHeapify(self, pos):
 
        
        
        if not self.isLeaf(pos):
            if (self.Heap[pos] > self.Heap[self.leftChild(pos)] or
               self.Heap[pos] > self.Heap[self.rightChild(pos)]):
 
                
                
                if self.Heap[self.leftChild(pos)] < self.Heap[self.rightChild(pos)]:
                    self.swap(pos, self.leftChild(pos))
                    self.minHeapify(self.leftChild(pos))
 
                
                
                else:
                    self.swap(pos, self.rightChild(pos))
                    self.minHeapify(self.rightChild(pos))
 
    
    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)
 
    
    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]))
 
    
    
    def minHeap(self):
 
        for pos in range(self.size//2, 0, -1):
            self.minHeapify(pos)
 
    
    
    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
 
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()))

Ausgabe : 

Der Min Heap ist
 ELTERN: 3 LINKSKIND: 5 RECHTSKIND: 6
 ELTERN: 5 LINKSKIND: 9 RECHTSKIND: 84
 ELTERN: 6 LINKSKIND: 19 RECHTSKIND: 17
 ELTERN: 9 LINKSKIND: 22 RECHTSKIND: 10
Der Mindestwert beträgt 3

Verwenden von Bibliotheksfunktionen:

Wir verwenden die Heapq- Klasse, um Heaps in Python zu implementieren. Standardmäßig wird Min Heap von dieser Klasse implementiert.  

 
from heapq import heapify, heappush, heappop
 
heap = []
heapify(heap)
 
heappush(heap, 10)
heappush(heap, 30)
heappush(heap, 20)
heappush(heap, 400)
 
print("Head value of heap : "+str(heap[0]))
 
print("The heap elements : ")
for i in heap:
    print(i, end = ' ')
print("\n")
 
element = heappop(heap)
 
print("The heap elements : ")
for i in heap:
    print(i, end = ' ')

Ausgabe :  

Kopfwert des Haufens: 10
Die Heap-Elemente:
10 30 20 400
Die Heap-Elemente:
20 30 400