Detailed explanation of PHP sorting algorithm heap sort

This article mainly introduces the sorting heap sort (Heap Sort) algorithm in PHP to everyone in detail. It has certain reference value. Interested friends can refer to it. I hope it can help everyone.

Algorithm introduction:

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

As mentioned before, simple selection sorting, it Selecting the smallest record among n records to be sorted requires n - 1 comparisons. This is understandable. It is normal to find the first data and need to compare it 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’s first introduce the heap:

The definition in "Dahua Data Structure": Heap It 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 the value of its left and right nodes, becoming Small top pile (small root pile).

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:

①Build a heap. Building a heap is a process of constantly adjusting the heap, starting from len/2 until you reach the first node, here 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).

②Adjustment heap: Adjustment heap will be used in the process of building the heap, and will also be used in the heap sorting process. The idea of ​​​​utilizing is to compare node i and its child nodes left(i), 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 sorting: Heap sorting 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);

Time complexity analysis:

Its running time is as long as it is consumed in Initial build pairs and iterative sifting through the rebuild pile.

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.

Related recommendations:

Detailed explanation of direct selection sorting of PHP sorting algorithm series

Detailed explanation of merge sorting of PHP sorting algorithm

Detailed explanation of bucket sorting in PHP sorting algorithm series_php skills

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