Lernen Sie die Prinzipien und die Zeitkomplexitätsanalyse des Heap-Sortieralgorithmus in PHP kennen.

Lernen Sie die Prinzipien und die zeitliche Komplexitätsanalyse des Heap-Sortieralgorithmus in PHP kennen.

Heap-Sortierung ist ein Sortieralgorithmus, der auf der Heap-Datenstruktur basiert und dessen zeitliche Komplexität O(nlogn) ist. In diesem Artikel werden die Prinzipien des Heap-Sortieralgorithmus in der PHP-Sprache vorgestellt und Codebeispiele bereitgestellt.

1. Die Definition und Eigenschaften eines Heaps

Bevor Sie die Heap-Sortierung lernen, müssen Sie zunächst die Definition und Eigenschaften eines Heaps verstehen. Ein Heap ist ein vollständiger Binärbaum, in dem der Wert jedes Knotens größer oder gleich dem Wert seiner untergeordneten Knoten ist. Wir nennen einen solchen Heap einen Big-Max-Heap. Wenn dagegen der Wert jedes Knotens kleiner oder gleich dem Wert seines untergeordneten Knotens ist, nennen wir ihn einen kleinen oberen Heap.

Aufgrund der Eigenschaften des Heaps ist das oberste Element des Heaps der Maximal- oder Minimalwert. Daher betrachten wir bei der Heap-Sortierung das zu sortierende Array normalerweise als vollständigen Binärbaum und verwenden dafür die Eigenschaften des Heaps Sortierung.

2. Prinzip des Heap-Sortieralgorithmus

Der Heap-Sortieralgorithmus ist hauptsächlich in zwei Schritte unterteilt: Erstellen eines Heaps und Anpassen des Heaps.

1. Heap erstellen: Passen Sie das Array so an, dass es in einen großen oberen Heap sortiert wird.

Die Schritte sind wie folgt:

• Durchlaufen Sie einen nach dem anderen vorwärts, beginnend beim letzten Nicht-Blattknoten (d. h. n/2-1) und rufen Sie die Funktion zum Anpassen des Heaps (adjustHeap) auf.
• Die Funktion zum Anpassen des Heaps verwendet einen Top-Down-Ansatz, um den aktuellen Knoten und seinen Unterbaum anzupassen, um sicherzustellen, dass der aktuelle Knoten größer als seine untergeordneten Knoten ist.
• Wiederholen Sie die beiden oben genannten Schritte, bis das gesamte Array zu einem großen oberen Heap angepasst ist.

2. AdjustHeap: Passen Sie den aktuellen Knoten und seinen Unterbaum in einen großen oberen Heap an.

Die Schritte sind wie folgt:

• Berechnen Sie die Positionen seiner linken und rechten untergeordneten Knoten basierend auf der Position des aktuellen Knotens.
• Vergleichen Sie die Werte des aktuellen Knotens und seiner linken und rechten untergeordneten Knoten, um die Position des größten Knotens zu ermitteln.
• Wenn die Position des maximalen Knotens nicht die Position des aktuellen Knotens ist, tauschen Sie die Werte des maximalen Knotens und des aktuellen Knotens aus und rufen Sie sich selbst rekursiv auf, um den ausgetauschten Teilbaum anzupassen.

3. Sort (sortHeap): Tauschen Sie das oberste Element des Heaps (d. h. das erste Element des Arrays) mit dem letzten Blattknoten aus und führen Sie dann eine Heap-Anpassung für die verbleibenden n-1 Elemente durch.

Die Schritte sind wie folgt:

• Tauschen Sie das oberste Element des Heaps mit dem letzten Blattknoten aus.
• Reduzieren Sie den Umfang des Heaps, dh ignorieren Sie den letzten sortierten Blattknoten.
• Anpassungen am Heap mit reduzierter Reichweite, um die Beschaffenheit des großen oberen Heaps beizubehalten.
• Wiederholen Sie die obigen drei Schritte, bis der Bereich des Heaps auf 1 reduziert ist.

3. PHP-Codebeispiel

Das Folgende ist ein Beispielcode für die Implementierung des Heap-Sortieralgorithmus in der PHP-Sprache:

function heapSort(&$arr) {
    $length = count($arr);

    // 构建大顶堆
    for ($i = floor($length/2 - 1); $i >= 0; $i--) {
        adjustHeap($arr, $i, $length);
    }

    // 调整堆并排序
    for ($i = $length - 1; $i >= 0; $i--) {
        // 交换堆顶元素和最后一个叶子节点
        $temp = $arr[0];
        $arr[0] = $arr[$i];
        $arr[$i] = $temp;

        // 调整堆使其保持大顶堆性质
        adjustHeap($arr, 0, $i);
    }
}

function adjustHeap(&$arr, $i, $length) {
    $largest = $i; // 最大值的位置
    $left = $i * 2 + 1; // 左子节点的位置
    $right = $i * 2 + 2; // 右子节点的位置

    // 比较当前节点与左右子节点的值，找到最大值的位置
    if ($left < $length && $arr[$left] > $arr[$largest]) {
        $largest = $left;
    }
    if ($right < $length && $arr[$right] > $arr[$largest]) {
        $largest = $right;
    }

    // 如果最大值的位置不是当前节点的位置，则交换两个位置的值，并递归调整堆
    if ($largest != $i) {
        $temp = $arr[$i];
        $arr[$i] = $arr[$largest];
        $arr[$largest] = $temp;
        adjustHeap($arr, $largest, $length);
    }
}

// 测试
$arr = [8, 3, 6, 2, 9, 1];
heapSort($arr);
print_r($arr); // 输出 [1, 2, 3, 6, 8, 9]

4. Die Zeitkomplexität der Heap-Sortierung beträgt O(nlogn). Unter diesen beträgt die zeitliche Komplexität des Aufbaus des Heaps O(n) und die zeitliche Komplexität der Anpassung des Heaps beträgt O(logn). Da n Elemente sortiert werden müssen, beträgt die Gesamtzeitkomplexität O(nlogn).

Zusammenfassung

In diesem Artikel werden die Prinzipien des Heap-Sortieralgorithmus in der PHP-Sprache ausführlich vorgestellt und entsprechende Codebeispiele bereitgestellt. Heap Sort ist ein effizienter Sortieralgorithmus, der sich für die Sortierung großer Arrays eignet. Durch das Erlernen des Heap-Sortieralgorithmus können Sie Ihr Verständnis und Ihre Anwendungsmöglichkeiten für Datenstrukturen und Algorithmen weiter verbessern.

Das obige ist der detaillierte Inhalt vonLernen Sie die Prinzipien und die Zeitkomplexitätsanalyse des Heap-Sortieralgorithmus in PHP kennen.. Für weitere Informationen folgen Sie bitte anderen verwandten Artikeln auf der PHP chinesischen Website!