Implementieren Sie Min Heap in Python

1. Der Min-Heap in Python
2. Erstellen Sie eine Klasse zum Implementieren von Min Heap in Python
3. Verwenden Sie das heapq-Modul, um Min Heap in Python zu implementieren

Bäume sind eine nichtlineare Datenstruktur, in der Elemente auf mehreren Ebenen angeordnet sind. Heap ist eine Datenstruktur, die auf Bäumen basiert.

Es ist ein vollständiger binärer Baum, was bedeutet, dass jeder übergeordnete Knoten zwei untergeordnete Knoten hat. Heaps implementieren verschiedene Algorithmen, sortieren andere Strukturen, priorisieren Warteschlangen usw.

Es gibt zwei Arten von Heaps - Max und Min. Diese basieren auf dem Wert des untergeordneten Knotens im Vergleich zum übergeordneten Knoten.

Dieses Tutorial behandelt den Min Heap und seine Implementierung in Python.

Der Min-Heap in Python

Jeder übergeordnete Knoten ist kleiner oder gleich dem untergeordneten Knoten in einem Min-Heap. Es folgt die aufsteigende Reihenfolge, und die Priorität liegt immer beim kleineren Knoten.

Für einen gegebenen Knoten n befindet sich sein linkes Kind bei 2n+1 und das rechte bei 2n+2.

Siehe folgendes Bild.

In Python kann der Min Heap auf zwei Arten implementiert werden. Diese werden unten besprochen.

Erstellen Sie eine Klasse zum Implementieren von Min Heap in Python

Wir können eine Klasse erstellen, um den Min Heap in Python zu implementieren. Wir werden das Klassenobjekt mit der Größe des Haufens initiieren und Methoden definieren, um den Einfügungsprozess von Elementen durchzuführen und sie ihren jeweiligen Indizes zuzuordnen.

Beispiel:

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()

Ausgang:

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

Die Methode insert() fügt dem Heap Elemente hinzu. Der Index und die Reihenfolge der Elemente werden mit der Methode swap() verwaltet, die die Funktionen rt_child_index() und lt_child_index() verwendet, um die Ebenen der untergeordneten Knoten basierend auf dem Wert der übergeordneten Knoten anzupassen.

Der Min Heap wird iteriert und mit der Funktion print_heap() der Klasse in einer Sequenz angezeigt.

Verwenden Sie das heapq-Modul, um Min Heap in Python zu implementieren

Python stellt ein heapq-Modul bereit, das die Heap-Datenstruktur implementieren kann, ohne andere Klassen zu erstellen. Dieses Modul stellt sicher, dass jedes Mal das kleinste Element des Heaps entfernt wird, um die Min Heap-Struktur beizubehalten.

Wir werden eine Liste verwenden, um die Knoten des Haufens zu verwalten. Die Elemente werden mit der Funktion heappush() hinzugefügt und die Reihenfolge wird entsprechend beibehalten, sodass die Struktur von Min Heap erhalten bleibt.

Der heappop() holt das kleinste Element aus dem Heap, den Wurzelknoten.

Beispiel:

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)

Ausgang:

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

Im obigen Beispiel haben wir eine Liste lst verwendet, um den Heap zu verwalten. Die Elemente werden hinzugefügt und ihre Reihenfolge wird automatisch mit der Funktion heappush() angepasst.

Der Min-Heap wird angezeigt. Der Elternknoten wird mit der Methode heappop() gepoppt und angezeigt.

Die verbleibenden untergeordneten Knoten werden auch nach dem Entfernen des übergeordneten Knotens angezeigt.