PHP implements sorting heap sort algorithm

This article mainly introduces the Heap Sort algorithm implemented in PHP in detail. It has certain reference value. Interested friends can refer to the

algorithm introduction:

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

As mentioned before, simple selection sorting selects the smallest one among the n records to be sorted. Records need to be compared n - 1 times. 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 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 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 only It is consumed in the initial build pair and repeated screening of 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.

Heap sort is an unstable sorting method.

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

Articles you may be interested in:

PHP simple selection sorting algorithm learning

Detailed explanation of WeChat Tiaoyitiao PHP code implementation

#Explanation of the function of sharing WeChat to Moments and recording the number of sharings implemented in PHP

##

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