Understand the principles and implementation of the heap sort algorithm in PHP?

Understand the principles and implementation methods of the heap sort algorithm in PHP?

In computer science, Heap Sort is an efficient sorting algorithm that takes advantage of the characteristics of the binary heap data structure. Heap sort can sort an unordered array into an ordered array with O(nlogn) time complexity.

The principle of heap sorting is to achieve sorting by establishing a maximum heap (or minimum heap). The maximum heap means that the key value of the parent node is always greater than (or equal to) the key value of its child node, and the opposite is true for the minimum heap. The steps for heap sorting are as follows:

1. Build a maximum heap: Construct an unordered array into a maximum heap such that the value of each parent node is greater than (or equal to) the value of its child node. The specific operation is to start from the last non-leaf node, perform a "sink" operation on each node, and exchange it with its child nodes until the maximum heap requirement is met.
2. Exchange and adjust: Swap the root node of the maximum heap (i.e., the first element of the array) with the last element, that is, put the maximum value in the last position. Then, the remaining first n-1 elements are resized into a max-heap.
3. Repeat step 2 until all elements are sorted.

The following is a sample code that uses PHP to implement the heap sort algorithm:

// 堆排序
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);

The above code implements the array-based heap sort algorithm. By calling the heapSort() function, you can sort an unordered array and output the result.

The heap sort algorithm is an efficient and stable sorting algorithm that can still maintain high performance when processing large amounts of data. It is very important for developers to understand and master the principles and implementation methods of heap sort. I hope the above content can help you understand the heap sort algorithm in PHP.

The above is the detailed content of Understand the principles and implementation of the heap sort algorithm in PHP?. For more information, please follow other related articles on the PHP Chinese website!