PHP heap sort algorithm example analysis

This time I will bring you an example analysis of the PHP heap sort algorithm. What are the precautions for the example analysis of the PHP heap sort algorithm? The following is a practical case, let's take a look.

As mentioned before, it is simple Selection sorting. It needs to compare n - 1 times to select the smallest record among the n records to be sorted. This is also understandable. To find the first It is normal for a data to need to be compared so many times, otherwise how to know that it is the smallest record.

Unfortunately, this operation does not save the comparison results of each trip. The comparison results in the latter trip are heavier. Many comparisons have been made in the previous trip, but due to the previous trip These comparison results were not saved during sorting, so these comparison operations were repeated during the next sorting pass, so a larger number of comparisons were recorded.

If we can select the smallest record each time and make corresponding adjustments to other records based on the comparison results, the overall efficiency of sorting will be very high. Heap sort is an improvement on simple selection sort, and the effect of this improvement is very obvious.

Basic idea:

Before introducing heap sorting, let us first introduce the heap:

"Dahua Data Structure" 》Definition in: A heap is a complete binary tree with the following properties: the value of each node is greater than or equal to the value of its left and right child nodes, becoming a big top heap (big root heap); or the value of each node is less than or equal to its The values ​​of the left and right nodes become the small top heap (small root heap).

When I saw this, I also had doubts about "whether the heap is a complete binary tree." There are also people on the Internet who say that it is not a complete binary tree, but regardless of whether the heap is a complete binary tree, I still reserve my opinion. We only need to know that here we use a large root heap (small root heap) in the form of a complete binary tree, mainly to facilitate storage and calculation (we will see the convenience later).

Heap sorting algorithm:

Heap sorting is a method of sorting using a heap (assuming a large root heap). Its basic The idea is: Construct the sequence to be sorted into a large root heap. At this time, the maximum value of the entire sequence is the root node at the top of the heap. Remove it (in fact, exchange it with the last element of the heap array, at which time the last element is the maximum value), and then reconstruct the remaining n - 1 sequences into a heap, so that you will get the n elements The next smallest value. If you execute this repeatedly, you can get an ordered sequence.

Basic operations of the large root heap sorting algorithm:

①Building a heap, building a heap is a process of constantly adjusting the heap , start adjusting from len/2 to the first node, where len is the number of elements in the heap. The process of building a heap is a linear process. The process of adjusting the heap is always called from len/2 to 0, which is equivalent to o(h1) o(h2) ... o(hlen/2) where h represents the depth of the node, len/2 Represents the number of nodes. This is a summation process, and the result is linear O(n).

②Adjust heap: Adjust heap will be used in the process of building the heap, and will also be used in the heap sorting process. The idea is to compare node i with its child nodes left(i) and right(i), and select the largest (or smallest) of the three. If the largest (smallest) value is not node i but one of its child nodes, There, node i interacts with the node, and then calls the heap adjustment process. This is a recursive process. The time complexity of the process of adjusting the heap is related to the depth of the heap. It is an operation of lgn because it is adjusted along the depth direction.

③Heap sort: Heap sort is performed using the above two processes. The first is to build a heap based on elements. Then take out the root node of the heap (usually exchange it with the last node), continue the heap adjustment process with the first len-1 nodes, and then take out the root node, until all nodes have been taken out. The time complexity of the heap sort process is O(nlgn). Because the time complexity of building a heap is O(n) (one call); the time complexity of adjusting the heap is lgn, and it is called n-1 times, so the time complexity of heap sorting is O(nlgn).

This process requires a lot of diagrams to understand clearly, but I am lazy. . . . . .

Algorithm implementation:

<?php
//堆排序（对简单选择排序的改进）
function swap(array &$arr,$a,$b){
  $temp = $arr[$a];
  $arr[$a] = $arr[$b];
  $arr[$b] = $temp;
}
//调整 $arr[$start]的关键字，使$arr[$start]、$arr[$start+1]、、、$arr[$end]成为一个大根堆（根节点最大的完全二叉树）
//注意这里节点 s 的左右孩子是 2*s + 1 和 2*s+2 （数组开始下标为 0 时）
function HeapAdjust(array &$arr,$start,$end){
  $temp = $arr[$start];
  //沿关键字较大的孩子节点向下筛选
  //左右孩子计算（我这里数组开始下标识 0）
  //左孩子2 * $start + 1，右孩子2 * $start + 2
  for($j = 2 * $start + 1;$j <= $end;$j = 2 * $j + 1){
    if($j != $end && $arr[$j] < $arr[$j + 1]){
      $j ++; //转化为右孩子
    }
    if($temp >= $arr[$j]){
      break; //已经满足大根堆
    }
    //将根节点设置为子节点的较大值
    $arr[$start] = $arr[$j];
    //继续往下
    $start = $j;
  }
  $arr[$start] = $temp;
}
function HeapSort(array &$arr){
  $count = count($arr);
  //先将数组构造成大根堆（由于是完全二叉树，所以这里用floor($count/2)-1，下标小于或等于这数的节点都是有孩子的节点)
  for($i = floor($count / 2) - 1;$i >= 0;$i --){
    HeapAdjust($arr,$i,$count);
  }
  for($i = $count - 1;$i >= 0;$i --){
    //将堆顶元素与最后一个元素交换，获取到最大元素（交换后的最后一个元素），将最大元素放到数组末尾
    swap($arr,0,$i);
    //经过交换，将最后一个元素（最大元素）脱离大根堆，并将未经排序的新树($arr[0...$i-1])重新调整为大根堆
    HeapAdjust($arr,0,$i - 1);
  }
}
$arr = array(9,1,5,8,3,7,4,6,2);
HeapSort($arr);
var_dump($arr);

Running results:

array(9) {
 [0]=>
 int(1)
 [1]=>
 int(2)
 [2]=>
 int(3)
 [3]=>
 int(4)
 [4]=>
 int(5)
 [5]=>
 int(6)
 [6]=>
 int(7)
 [7]=>
 int(8)
 [8]=>
 int(9)
}

时间复杂度分析：

它的运行时间只要是消耗在初始构建对和在重建堆屎的反复筛选上。

总体上来说，堆排序的时间复杂度是 O(nlogn)。由于堆排序对原始记录的排序状态并不敏感，因此它无论是最好、最差和平均时间复杂度都是 O(nlogn)。这在性能上显然要远远好于冒泡、简单选择、直接插入的 O(n^2) 的时间复杂度了。

堆排序是一种不稳定排序方法。

相信看了本文案例你已经掌握了方法，更多精彩请关注php中文网其它相关文章！

推荐阅读：

PHP原型设计模式使用案例分析

PHP基数排序使用步骤详解

The above is the detailed content of PHP heap sort algorithm example analysis. For more information, please follow other related articles on the PHP Chinese website!