Learn the principles and time complexity analysis of the heap sort algorithm in PHP.

Learn the principles and time complexity analysis of the heap sort algorithm in PHP

Heap sort is a sorting algorithm based on the heap data structure, and its time complexity is O(nlogn). This article will introduce the principles of the heap sort algorithm in the PHP language and provide code examples.

1. The definition and properties of a heap

Before learning heap sorting, you first need to understand the definition and properties of a heap. A heap is a complete binary tree in which the value of each node is greater than or equal to the value of its child nodes. We call such a heap a big-max heap. On the contrary, if the value of each node is less than or equal to the value of its child node, we call it a small top heap.

Due to the characteristics of the heap, the top element of the heap is the maximum or minimum value. Therefore, in heap sorting, we usually regard the array to be sorted as a complete binary tree and use the characteristics of the heap for sorting.

2. Principle of heap sort algorithm

The heap sort algorithm is mainly divided into two steps: building a heap and adjusting the heap.

1. Build Heap: Adjust the array to be sorted into a large top heap.

The steps are as follows:

• Traverse forward one by one starting from the last non-leaf node (i.e. n/2-1), and call the function of adjusting the heap (adjustHeap).
• The function of adjusting the heap adopts a top-down approach to adjust the current node and its subtree to ensure that the current node is larger than its child nodes.
• Repeat the above two steps until the entire array is adjusted to a large top heap.

2. AdjustHeap: Adjust the current node and its subtree into a large top heap.

The steps are as follows:

• Calculate the positions of its left and right child nodes based on the position of the current node.
• Compare the values ​​of the current node and its left and right child nodes to find the position of the largest node.
• If the position of the maximum node is not the position of the current node, exchange the values ​​of the maximum node and the current node, and call itself recursively to adjust the exchanged subtree.

3. Sort (sortHeap): Exchange the top element of the heap (that is, the first element of the array) with the last leaf node, and then perform heap adjustments on the remaining n-1 elements.

The steps are as follows:

• Exchange the top element of the heap with the last leaf node.
• Reduce the scope of the heap, that is, ignore the last leaf node that has been sorted.
• Adjust the reduced range heap to maintain the nature of the large top heap.
• Repeat the above three steps until the range of the heap is reduced to 1.

3. PHP code example

The following is an example code for implementing the heap sort algorithm in PHP language:

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. Time complexity analysis

The time complexity of heap sorting is O(nlogn). Among them, the time complexity of building the heap is O(n), and the time complexity of adjusting the heap is O(logn). Since n elements need to be sorted, the total time complexity is O(nlogn).

Summary

This article introduces the principles of the heap sort algorithm in the PHP language in detail and provides corresponding code examples. Heap sort is an efficient sorting algorithm suitable for large arrays to be sorted. By learning the heap sort algorithm, you can further improve your understanding and application capabilities of data structures and algorithms.

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