Bagaimana untuk menulis algoritma isihan timbunan menggunakan PHP

Cara menulis algoritma pengisihan timbunan menggunakan PHP

Isihan timbunan ialah algoritma pengisihan yang cekap Idea terasnya ialah untuk membina urutan untuk diisih ke dalam timbunan binari, dan kemudian melaraskan struktur timbunan untuk mencapai pengisihan. Artikel ini akan memperkenalkan cara menulis algoritma isihan timbunan menggunakan PHP dan menyediakan contoh kod untuk rujukan.

1. Definisi timbunan
   Sebelum mula menulis algoritma isihan timbunan, anda perlu terlebih dahulu menjelaskan definisi dan sifat timbunan. Timbunan ialah pokok binari lengkap dengan sifat berikut: untuk mana-mana nod i, dua syarat berikut dipenuhi:
2. Nilai nod induk sentiasa lebih besar daripada atau sama dengan nilai nod anak (timbunan maksimum);
3. Nilai nod induk sentiasa kurang daripada Atau sama dengan nilai nod anak (timbunan min).
4. Melaraskan operasi timbunan
   Untuk membina timbunan, kita perlu memahami cara melakukan operasi pelarasan timbunan. Pelarasan timbunan dibahagikan kepada dua langkah:
5. Mulakan dari nod bukan daun terakhir, bandingkan nod dengan nod anaknya secara bergilir, dan tukar nilai yang lebih besar (atau lebih kecil) kepada kedudukan nod induk
6. Ulangi Langkah di atas sehingga struktur keseluruhan timbunan memenuhi sifat timbunan.

Berikut ialah contoh fungsi pelarasan timbunan yang dilaksanakan dalam PHP:

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. Algoritma pengisihan timbunan
   Selepas mempunyai takrifan timbunan dan operasi pelarasan timbunan, anda boleh menulis algoritma pengisihan timbunan. Langkah utama pengisihan timbunan adalah seperti berikut:
4. Bina timbunan maksimum: Bermula dari nod bukan daun terakhir, panggil fungsi pelarasan timbunan dalam urutan untuk membina timbunan maksimum
5. Isih: Tukar elemen atas (nilai maksimum ) timbunan dengan kedudukan elemen terakhir, kemudian kurangkan saiz timbunan sebanyak 1, dan kemudian panggil fungsi pelarasan timbunan untuk melaraskan susunan elemen yang tinggal
6. Ulang langkah di atas sehingga saiz timbunan ialah 1; , pada masa itu semua elemen disusun dalam tertib menaik.

Berikut ialah contoh fungsi isihan timbunan yang dilaksanakan dalam PHP:

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. Menggunakan algoritma isihan timbunan
   Menggunakan algoritma isihan timbunan adalah sangat mudah Anda hanya perlu menghantar tatasusunan untuk diisih sebagai parameter fungsi isihan timbunan di atas. Berikut ialah contoh pengisihan tatasusunan menggunakan algoritma isihan timbunan:

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

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

heapSort($arr);

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

Menjalankan kod di atas, anda akan mendapat output berikut:

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

Dengan cara ini, kami telah berjaya menulis dan menggunakan algoritma isihan timbunan menggunakan PHP .

Ringkasan:
Isihan timbunan ialah algoritma pengisihan yang cekap yang melaksanakan pengisihan dengan membina timbunan maksimum (atau minimum). Dengan melaraskan struktur timbunan, kami boleh melaksanakan pengisihan timbunan dengan mudah. Menulis algoritma isihan timbunan menggunakan PHP adalah agak mudah Anda hanya perlu menulis fungsi pelarasan timbunan dan fungsi isihan timbunan, dan lulus tatasusunan untuk diisih sebagai parameter untuk mencapai pengisihan. Saya harap kandungan artikel ini dapat memberikan sedikit bantuan untuk anda memahami dan menggunakan algoritma isihan timbunan.

Atas ialah kandungan terperinci Bagaimana untuk menulis algoritma isihan timbunan menggunakan PHP. Untuk maklumat lanjut, sila ikut artikel berkaitan lain di laman web China PHP!