So schreiben Sie einen Heap-Sortieralgorithmus mit PHP

So schreiben Sie einen Heap-Sortieralgorithmus mit PHP

Heap-Sortierung ist ein effizienter Sortieralgorithmus. Seine Kernidee besteht darin, die zu sortierende Sequenz in einen binären Heap zu konstruieren und dann die Struktur des Heaps kontinuierlich anzupassen, um eine Sortierung zu erreichen. In diesem Artikel wird das Schreiben eines Heap-Sortieralgorithmus mit PHP vorgestellt und Codebeispiele als Referenz bereitgestellt.

1. Definition des Heaps
   Bevor Sie mit dem Schreiben des Heap-Sortieralgorithmus beginnen, müssen Sie zunächst die Definition und die Eigenschaften des Heaps klären. Ein Heap ist ein vollständiger Binärbaum mit den folgenden Eigenschaften: Für jeden Knoten i sind die folgenden zwei Bedingungen erfüllt:
2. Der Wert des übergeordneten Knotens ist immer größer oder gleich dem Wert des untergeordneten Knotens (maximaler Heap);
3. Der Wert des übergeordneten Knotens ist immer kleiner oder gleich dem Wert des untergeordneten Knotens (Min-Heap).
4. Anpassen von Heap-Vorgängen
   Um einen Heap zu erstellen, müssen wir verstehen, wie Heap-Anpassungsvorgänge durchgeführt werden. Die Anpassung des Heaps ist in zwei Schritte unterteilt:
5. Beginnen Sie mit dem letzten Nicht-Blattknoten, vergleichen Sie den Knoten nacheinander mit seinen untergeordneten Knoten und tauschen Sie den größeren (oder kleineren) Wert gegen die Position des übergeordneten Knotens aus
6. Wiederholen Sie die obigen Schritte, bis die Struktur des gesamten Heaps den Eigenschaften des Heaps entspricht.

Das Folgende ist ein Beispiel für eine in PHP implementierte Heap-Anpassungsfunktion:

function heapify(&$arr, $n, $i) {
    $largest = $i; // 将当前节点标记为最大值节点
    $l = 2 * $i + 1; // 左子节点
    $r = 2 * $i + 2; // 右子节点

    // 如果左子节点大于根节点
    if ($l < $n && $arr[$l] > $arr[$largest]) {
        $largest = $l;
    }

    // 如果右子节点大于根节点
    if ($r < $n && $arr[$r] > $arr[$largest]) {
        $largest = $r;
    }

    // 如果最大值不等于当前节点，则交换它们的位置
    if ($largest != $i) {
        $temp = $arr[$i];
        $arr[$i] = $arr[$largest];
        $arr[$largest] = $temp;

        // 递归调整交换之后的子树
        heapify($arr, $n, $largest);
    }
}

3. Heap-Sortieralgorithmus
   Nachdem Sie die Definition des Heaps und die Heap-Anpassungsoperation erstellt haben, können Sie den Heap-Sortieralgorithmus schreiben. Die Hauptschritte der Heap-Sortierung sind wie folgt:
4. Erstellen eines maximalen Heaps: Rufen Sie ausgehend vom letzten Nicht-Blattknoten nacheinander die Heap-Anpassungsfunktion auf, um einen maximalen Heap zu erstellen;
5. Sortieren: Tauschen Sie das oberste Element aus (Maximalwert). ) des Heaps mit der letzten Elementposition, verringern Sie dann die Größe des Heaps um 1 und rufen Sie dann die Heap-Anpassungsfunktion auf, um die Reihenfolge der verbleibenden Elemente anzupassen.
6. Wiederholen Sie die obigen Schritte, bis die Größe des Heaps 1 beträgt , wobei alle Elemente in aufsteigender Reihenfolge angeordnet sind.

Das Folgende ist ein Beispiel für eine in PHP implementierte Heap-Sortierfunktion:

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

    // 构建最大堆
    for ($i = ($n / 2) - 1; $i >= 0; $i--) {
        heapify($arr, $n, $i);
    }

    // 排序
    for ($i = $n - 1; $i > 0; $i--) {
        // 交换堆顶和最后一个元素
        $temp = $arr[0];
        $arr[0] = $arr[$i];
        $arr[$i] = $temp;

        // 调整剩余元素的顺序
        heapify($arr, $i, 0);
    }
}

4. Verwendung des Heap-Sortieralgorithmus
   Die Verwendung des Heap-Sortieralgorithmus ist sehr einfach. Sie müssen nur das zu sortierende Array als Parameter übergeben die obige Heap-Sortierfunktion. Das Folgende ist ein Beispiel für das Sortieren eines Arrays mit dem Heap-Sortieralgorithmus:

$arr = [3, 7, 2, 11, 1, 9, 6, 4, 8];

echo "排序前：" . implode(", ", $arr) . "
";

heapSort($arr);

echo "排序后：" . implode(", ", $arr) . "
";

Wenn Sie den obigen Code ausführen, erhalten Sie die folgende Ausgabe:

排序前：3, 7, 2, 11, 1, 9, 6, 4, 8
排序后：1, 2, 3, 4, 6, 7, 8, 9, 11

Auf diese Weise haben wir den Heap-Sortieralgorithmus mit PHP erfolgreich geschrieben und angewendet .

Zusammenfassung:
Heap-Sortierung ist ein effizienter Sortieralgorithmus, der die Sortierung durch Aufbau eines maximalen (oder minimalen) Heaps implementiert. Durch Anpassen der Struktur des Heaps können wir die Heap-Sortierung problemlos implementieren. Das Schreiben eines Heap-Sortieralgorithmus mit PHP ist relativ einfach. Sie müssen lediglich eine Heap-Anpassungsfunktion und eine Heap-Sortierfunktion schreiben und das zu sortierende Array als Parameter übergeben, um eine Sortierung zu erreichen. Ich hoffe, dass der Inhalt dieses Artikels Ihnen dabei helfen kann, den Heap-Sortieralgorithmus zu verstehen und zu verwenden.

Das obige ist der detaillierte Inhalt vonSo schreiben Sie einen Heap-Sortieralgorithmus mit PHP. Für weitere Informationen folgen Sie bitte anderen verwandten Artikeln auf der PHP chinesischen Website!