Fahami prinsip dan pelaksanaan algoritma isihan timbunan dalam PHP?

Fahami prinsip dan pelaksanaan algoritma isihan timbunan dalam PHP?

Dalam sains komputer, Heap Sort ialah algoritma pengisihan yang cekap yang mengambil kesempatan daripada ciri-ciri struktur data timbunan binari. Isihan timbunan boleh mengisih tatasusunan tidak tertib ke dalam tatasusunan tersusun dengan kerumitan masa O(nlogn).

Prinsip pengisihan timbunan adalah untuk mencapai pengisihan dengan mewujudkan timbunan maksimum (atau timbunan minimum). Timbunan maksimum bermakna nilai kunci nod induk sentiasa lebih besar daripada (atau sama dengan) nilai kunci nod anaknya, dan sebaliknya berlaku untuk timbunan minimum. Langkah-langkah isihan timbunan adalah seperti berikut:

1. Bina timbunan maks: Bina tatasusunan tidak tertib menjadi timbunan maks supaya nilai setiap nod induk lebih besar daripada (atau sama dengan) nilai nod anaknya. Operasi khusus adalah untuk bermula dari nod bukan daun terakhir, melakukan operasi "sink" pada setiap nod, dan menukarnya dengan nod anaknya sehingga keperluan timbunan maksimum dipenuhi.
2. Tukar dan laraskan: Tukar nod akar timbunan maksimum (iaitu elemen pertama tatasusunan) dengan elemen terakhir, iaitu, letakkan nilai maksimum pada kedudukan terakhir. Kemudian, unsur n-1 pertama yang tinggal diubah saiznya menjadi timbunan maks.
3. Ulang langkah 2 sehingga semua elemen disusun.

Berikut ialah contoh kod yang menggunakan PHP untuk melaksanakan algoritma isihan timbunan:

// 堆排序
function heapSort(&$arr) {
    $len = count($arr);
    // 构建最大堆
    buildHeap($arr, $len);
    
    // 交换并调整
    for ($i = $len - 1; $i > 0; $i--) {
        // 将当前最大值与最后一个元素交换
        swap($arr, 0, $i);
        // 重新调整为最大堆
        heapify($arr, 0, $i);
    }
}

// 构建最大堆
function buildHeap(&$arr, $len) {
    // 从最后一个非叶子节点开始逐个向上调整
    $startIndex = floor($len / 2) - 1;
    for ($i = $startIndex; $i >= 0; $i--) {
        heapify($arr, $i, $len);
    }
}

// 将指定节点及其子节点调整为最大堆
function heapify(&$arr, $index, $len) {
    $largest = $index; // 最大值的索引
    $leftChild = 2 * $index + 1; // 左子节点的索引
    $rightChild = 2 * $index + 2; // 右子节点的索引

    // 找出左、右子节点和当前节点中的最大值
    if ($leftChild < $len && $arr[$leftChild] > $arr[$largest]) {
        $largest = $leftChild;
    }
    if ($rightChild < $len && $arr[$rightChild] > $arr[$largest]) {
        $largest = $rightChild;
    }

    // 若最大值不是当前节点，交换两者的值，并递归地调整交换后的子堆
    if ($largest != $index) {
        swap($arr, $index, $largest);
        heapify($arr, $largest, $len);
    }
}

// 交换数组中两个元素的位置
function swap(&$arr, $i, $j) {
    $temp = $arr[$i];
    $arr[$i] = $arr[$j];
    $arr[$j] = $temp;
}

// 测试代码
$arr = [4, 10, 3, 5, 1];
heapSort($arr);
echo "排序结果：" . implode(", ", $arr);

Kod di atas melaksanakan algoritma isihan timbunan berasaskan tatasusunan. Dengan memanggil fungsi heapSort(), anda boleh mengisih tatasusunan tidak tertib dan mengeluarkan hasilnya.

Algoritma isihan timbunan ialah algoritma isihan yang cekap dan stabil yang masih boleh mengekalkan prestasi tinggi apabila memproses sejumlah besar data. Adalah sangat penting untuk pembangun memahami dan menguasai prinsip dan kaedah pelaksanaan jenis timbunan. Saya harap kandungan di atas dapat membantu anda memahami algoritma isihan timbunan dalam PHP.

Atas ialah kandungan terperinci Fahami prinsip dan pelaksanaan algoritma isihan timbunan dalam PHP?. Untuk maklumat lanjut, sila ikut artikel berkaitan lain di laman web China PHP!