PHP sorting algorithm Heap Sort (Heap Sort)

This article mainly introduces the PHP sorting algorithm Heap Sort, and analyzes the principles, implementation methods and related usage precautions of Heap Sort in detail in the form of examples. Friends in need can refer to it

The example in this article describes the PHP sorting algorithm Heap Sort. Share it with everyone for your reference, the details are as follows:

Algorithm introduction:

Here I directly quote the beginning of "Dahua Data Structure" ：

As mentioned before, simple selection sorting requires comparison n - 1 times to select the smallest record among the n records to be sorted. This is understandable. Finding the first data requires comparison like this Multiple times is normal, otherwise how to know he 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 result:

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)
}

Time complexity analysis:

Its running time is only consumed in the initial construction of the pair and in the reconstruction of the heap Repeated screening of shit.

In general, the time complexity of heap sort is O(nlogn). Since heap sort is not sensitive to the sorting state of the original records, its best, worst and average time complexity is O(nlogn). This is obviously far better in performance than the O(n^2) time complexity of bubbling, simple selection, and direct insertion.

Heap sort is an unstable sorting method.

This article is referenced from "Dahua Data Structure". It is only recorded here for future reference. Please don't criticize!

Related recommendations:

PHP sorting algorithm Radix Sort

PHP sorting algorithm Quick Sort (Quick Sort) and Its optimization

PHP sorting algorithm Merging Sort

The above is the detailed content of PHP sorting algorithm Heap Sort (Heap Sort). For more information, please follow other related articles on the PHP Chinese website!