Detaillierte Einführung in den binären Heap in Python (Codebeispiel)

Dieser Artikel bietet Ihnen eine detaillierte Einführung (Codebeispiel) zum Binärheap in Python. Ich hoffe, dass er Ihnen als Referenz dienen wird.

1. Heap

Datenstruktur Heap ist eine Prioritätswarteschlange. Eine Warteschlange ist eine First-In-First-Out-Datenstruktur. Eine wichtige Variante der Warteschlange ist die sogenannte Prioritätswarteschlange. Mithilfe der Prioritätswarteschlange können Objekte in beliebiger Reihenfolge hinzugefügt werden und das kleinste Element jederzeit gefunden (oder möglicherweise entfernt) werden (möglicherweise beim Hinzufügen von Objekten), was bedeutet, dass es effizienter ist als die min-Methode von Python.
In einer Prioritätswarteschlange wird die logische Reihenfolge der Elemente in der Warteschlange durch ihre Priorität bestimmt. Das Element mit der höchsten Priorität steht ganz vorne in der Warteschlange, das Element mit der niedrigsten Priorität ganz hinten. Wenn Sie Elemente in die Prioritätswarteschlange einreihen, rücken daher möglicherweise immer wieder neue Elemente in den Vordergrund.

2. Binäre Heap-Operationen

Die Grundoperationen unserer binären Heap-Implementierung sind wie folgt:

BinaryHeap() erstellt eine neue, leere Binärdatei Haufen.
insert(k) fügt dem Heap ein neues Element hinzu.
findMin() gibt das Element mit dem kleinsten Schlüsselwert zurück und belässt das Element im Heap.
delMin() Gibt das Element mit dem kleinsten Schlüsselwert zurück und entfernt das Element aus dem Heap.
Wenn der Heap leer ist, gibt isEmpty() true zurück, andernfalls false.
size() gibt die Anzahl der Elemente im Heap zurück.
buildHeap(list) Erstellt einen neuen Heap aus einer Liste von Schlüsseln.

Beachten Sie, dass unabhängig von der Reihenfolge, in der wir Elemente zum Heap hinzufügen, jedes Mal das kleinste entfernt wird.

Damit unser Heap effizient funktioniert, nutzen wir die logarithmische Natur binärer Bäume, um unseren Heap darzustellen. Um die logarithmische Leistung zu gewährleisten, müssen wir den Baum im Gleichgewicht halten. Ausgeglichener Binärbaum hat ungefähr die gleiche Anzahl von Knoten im linken und rechten Teilbaum der Wurzel, es handelt sich um einen leeren Baum oder der absolute Wert des Höhenunterschieds zwischen seinem linken und rechten Teilbaum überschreitet nicht 1, und die linken und rechten Teilbäume Die Teilbäume sind alle ausgeglichene Binärbäume. In unserer Heap-Implementierung halten wir den Baum im Gleichgewicht, indem wir einen vollständigen Binärbaum erstellen. Ein vollständiger Binärbaum ist ein Baum, in dem die Knoten auf jeder Ebene vollständig gefüllt sind. Wenn die letzte Ebene nicht voll ist, fehlen nur einige Knoten auf der rechten Seite. Abbildung 1 zeigt ein Beispiel eines vollständigen Binärbaums.
Eine weitere interessante Eigenschaft eines vollständigen Binärbaums ist, dass wir ihn mithilfe einer einzigen Liste darstellen können.

# from pythonds.trees.binheap import BinHeap
class BinHeap:
    def __init__(self):
        self.heapList = [0]
        self.currentSize = 0
    def insert(self,k):
        '''将项附加到列表的末尾，并通过比较新添加的项与其父项，我们可以重新获得堆结构属性。 '''
        self.heapList.append(k)
        self.currentSize = self.currentSize + 1
        self.percUp(self.currentSize)
    def buildHeap(self, alist):
        '''直接将整个列表生成堆，将总开销控制在O(n)'''
        i = len(alist) // 2
        self.currentSize = len(alist)
        self.heapList = [0] + alist[:]  # 分片法[:]建立一个列表的副本
        while (i > 0):
            self.percDown(i)
           i = i - 1
    def percUp(self,i):
        '''如果新添加的项小于其父项，则我们可以将项与其父项交换。'''
        while i // 2 > 0:    # // 取整除 - 返回商的整数部分（向下取整）
            if self.heapList[i] < self.heapList[i//2]:
               tmp = self.heapList[i // 2]
               self.heapList[i // 2] = self.heapList[i]
               self.heapList[i] = tmp
            i = i // 2
    def percDown(self, i):
        &#39;&#39;&#39;将新的根节点沿着一条路径“下沉”，直到比两个子节点都小。&#39;&#39;&#39;
        while (i * 2) <= self.currentSize:
            mc = self.minChild(i)
            if self.heapList[i] > self.heapList[mc]:
                tmp = self.heapList[i]
                self.heapList[i] = self.heapList[mc]
                self.heapList[mc] = tmp
            i = mc
    def minChild(self, i):
        &#39;&#39;&#39;在选择下沉路径时，如果新根节点比子节点大，那么选择较小的子节点与之交换。&#39;&#39;&#39;
        if i * 2 + 1 > self.currentSize:
            return i * 2
        else:
            if self.heapList[i * 2] < self.heapList[i * 2 + 1]:
                return i * 2
            else:
                return i * 2 + 1
    def delMin(self):
        &#39;&#39;&#39;移走根节点的元素（最小项）后如何保持堆结构和堆次序&#39;&#39;&#39;
        retval = self.heapList[1]
        self.heapList[1] = self.heapList[self.currentSize]
        self.currentSize = self.currentSize - 1
        self.heapList.pop()
        self.percDown(1)
        return retval
bh = BinHeap()
bh.buildHeap([9,5,6,2,3])
print(bh.delMin())
print(bh.delMin())
print(bh.delMin())
print(bh.delMin())
print(bh.delMin())

Der letzte Teil über binäre Heaps besteht darin, einen Weg zu finden, einen „Heap“ aus einer ungeordneten Liste zu generieren. Das erste, woran wir denken, ist, jedes Element in der ungeordneten Liste der Reihe nach in den Heap einzufügen. Für eine sortierte Liste können wir die binäre Suche verwenden, um die entsprechende Position zu finden, und dann den Schlüsselwert mit einer zeitlichen Komplexität von O(logn) an der nächsten Position in den Heap einfügen. Darüber hinaus erfordert das Einfügen eines Elements in die Liste das Verschieben einiger anderer Elemente der Liste, um Platz für den neuen Knoten zu schaffen, und die Zeitkomplexität beträgt O(n). Daher betragen die Gesamtkosten für die Verwendung der Einfügemethode O(nlogn). Tatsächlich können wir die gesamte Liste direkt in einem Heap generieren und den gesamten Overhead für O(n) steuern. Listing 6 zeigt den Vorgang zum Generieren eines Heaps.

Es erscheint ein wenig unglaublich, dass ein binärer Heap mit O(n)-Overhead generiert werden kann, deshalb werde ich es hier nicht beweisen. Der Schlüssel zum Verständnis, dass ein Heap mit O(n)-Overhead generiert werden kann, liegt jedoch darin, dass der Logn-Faktor auf der Höhe des Baums basiert. Bei vielen Vorgängen in buildHeap ist die Höhe des Baums kleiner als logn.

Das obige ist der detaillierte Inhalt vonDetaillierte Einführung in den binären Heap in Python (Codebeispiel). Für weitere Informationen folgen Sie bitte anderen verwandten Artikeln auf der PHP chinesischen Website!