Ketahui prinsip dan analisis kerumitan masa bagi algoritma isihan timbunan dalam PHP.

Ketahui prinsip dan analisis kerumitan masa algoritma isihan timbunan dalam PHP

Isihan timbunan ialah algoritma isihan berdasarkan struktur data timbunan, dan kerumitan masanya ialah O(nlogn). Artikel ini akan memperkenalkan prinsip algoritma isihan timbunan dalam bahasa PHP dan memberikan contoh kod.

1. Definisi dan sifat timbunan

Sebelum mempelajari pengisihan timbunan, anda perlu memahami definisi dan sifat timbunan. Timbunan ialah pokok perduaan lengkap di mana nilai setiap nod adalah lebih besar daripada atau sama dengan nilai nod anaknya Kami memanggil timbunan tersebut sebagai timbunan maksimum besar. Sebaliknya, jika nilai setiap nod adalah kurang daripada atau sama dengan nilai nod anaknya, kami memanggilnya timbunan atas kecil.

Disebabkan oleh ciri-ciri timbunan, elemen atas timbunan adalah nilai maksimum atau minimum Oleh itu, dalam pengisihan timbunan, kita biasanya menganggap tatasusunan itu sebagai pokok binari yang lengkap dan menggunakan ciri-ciri timbunan untuk. menyusun.

2. Prinsip algoritma isihan timbunan

Algoritma isihan timbunan terbahagi terutamanya kepada dua langkah: membina timbunan dan melaraskan timbunan.

1. Bina Timbunan: Laraskan tatasusunan untuk diisih ke dalam timbunan atas yang besar.

Langkahnya adalah seperti berikut:

• Traverse ke hadapan satu demi satu bermula dari nod bukan daun terakhir (iaitu n/2-1), dan panggil fungsi melaraskan timbunan (adjustHeap).
• Fungsi melaraskan timbunan menggunakan pendekatan atas ke bawah untuk melaraskan nod semasa dan subpokoknya untuk memastikan bahawa nod semasa lebih besar daripada nod anaknya.
• Ulang dua langkah di atas sehingga keseluruhan tatasusunan dilaraskan menjadi timbunan atas yang besar.

2. AdjustHeap: Laraskan nod semasa dan subpohonnya ke dalam timbunan atas yang besar.

Langkah-langkahnya adalah seperti berikut:

• Kira kedudukan nod anak kiri dan kanannya berdasarkan kedudukan nod semasa.
• Bandingkan nilai nod semasa dan nod anak kiri dan kanannya untuk mencari kedudukan nod terbesar.
• Jika kedudukan nod maksimum bukan kedudukan nod semasa, tukar nilai nod maksimum dan nod semasa, dan panggil sendiri secara rekursif untuk melaraskan subpokok yang ditukar.

3. Isih (sortHeap): Tukar elemen atas timbunan (iaitu elemen pertama tatasusunan) dengan nod daun terakhir, dan kemudian lakukan pelarasan timbunan pada unsur n-1 yang tinggal.

Langkah-langkahnya adalah seperti berikut:

• Tukar elemen atas timbunan dengan nod daun terakhir.
• Kurangkan skop timbunan iaitu abaikan nod daun terakhir yang telah disusun.
• Pelarasan kepada timbunan julat yang dikurangkan untuk mengekalkan sifat timbunan atas yang besar.
• Ulang tiga langkah di atas sehingga julat timbunan dikurangkan kepada 1.

3. Contoh kod PHP

Berikut ialah contoh kod untuk melaksanakan algoritma pengisihan timbunan dalam bahasa PHP:

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 Analisis kerumitan masa

Kerumitan masa pengisihan timbunan ialah O(nlogn). Antaranya, kerumitan masa membina timbunan ialah O(n), dan kerumitan masa melaraskan timbunan ialah O(logn). Oleh kerana n elemen perlu diisih, jumlah kerumitan masa ialah O(nlogn).

Ringkasan

Artikel ini memperkenalkan prinsip algoritma isihan timbunan dalam bahasa PHP secara terperinci dan menyediakan contoh kod yang sepadan. Isihan timbunan ialah algoritma pengisihan yang cekap sesuai untuk tatasusunan besar untuk diisih. Dengan mempelajari algoritma isihan timbunan, anda boleh meningkatkan lagi pemahaman anda dan keupayaan aplikasi struktur data dan algoritma.

Atas ialah kandungan terperinci Ketahui prinsip dan analisis kerumitan masa bagi algoritma isihan timbunan dalam PHP.. Untuk maklumat lanjut, sila ikut artikel berkaitan lain di laman web China PHP!