How to write a heap sort algorithm using PHP

How to use PHP to write a heap sort algorithm

Heap sort is an efficient sorting algorithm. Its core idea is to construct the sequence to be sorted into a binary heap, and then continuously adjust the structure of the heap to achieve sorting. This article will introduce how to write a heap sort algorithm using PHP and provide code examples for reference.

1. Definition of heap
   Before starting to write the heap sorting algorithm, you first need to clarify the definition and properties of the heap. The heap is a complete binary tree with the following properties: for any node i, the following two conditions are met:
2. The value of the parent node is always greater than or equal to the value of the child node (maximum heap);
3. The value of the parent node is always less than or equal to the value of the child node (minimum heap).
4. Adjusting heap operations
   In order to build a heap, we need to understand how to perform heap adjustment operations. The adjustment of the heap is divided into two steps:
5. Starting from the last non-leaf node, compare the node with its child nodes in turn, and exchange the larger (or smaller) value to the position of the parent node;
6. Repeat the above steps until the structure of the entire heap meets the properties of the heap.

The following is an example of a heap adjustment function implemented in 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. Heap sorting algorithm
   After having the definition of the heap and the heap adjustment operation, It’s time to write a heap sort algorithm. The main steps of heap sorting are as follows:
4. Construct the maximum heap: starting from the last non-leaf node, call the heap adjustment function in sequence to build a maximum heap;
5. Sort: add the top element of the heap ( maximum value) and exchange positions with the last element, then reduce the size of the heap by -1, and then call the heap adjustment function to adjust the order of the remaining elements;
6. Repeat the above steps until the size of the heap is 1, at which time all elements Sort in ascending order.

The following is an example of a heap sort function implemented in 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. Using the heap sort algorithm
   Using the heap sort algorithm is very simple. You only need to sort the Just pass the array as a parameter to the above heap sort function. The following is an example of using the heap sort algorithm to sort an array:

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

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

heapSort($arr);

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

Running the above code, you will get the following output:

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

In this way, we have successfully written and The heap sort algorithm is applied.

Summary:
Heap sort is an efficient sorting algorithm that implements sorting by building a maximum (or minimum) heap. By adjusting the structure of the heap, we can easily implement heap sorting. Writing a heap sort algorithm using PHP is relatively simple. You only need to write a heap adjustment function and a heap sort function, and pass the array to be sorted as a parameter to achieve sorting. I hope the content of this article can provide some help for you to understand and use the heap sort algorithm.

The above is the detailed content of How to write a heap sort algorithm using PHP. For more information, please follow other related articles on the PHP Chinese website!