Detailed explanation of PHP heap sort algorithm

This article mainly introduces the heap sorting algorithm implemented in PHP, and analyzes the principles, implementation steps and related operating techniques of PHP heap sorting in the form of examples. Friends in need can refer to it

The details are as follows:

Heap is the collective name for a special type of data structure in computer science, usually an array object that can be viewed as a tree.

Heap{k1,k2,ki,…,kn} (ki <= k2i,ki <= k2i 1)|(ki >= k2i,ki >= k2i 1), (i = 1,2,3,4...n/2)

About the heap:

The value of a node in the heap is always not greater than Or not less than the value of its parent node;
The heap is always a complete binary tree (below).
The heap with the largest root node is called the maximum heap or large root heap, and the heap with the smallest root node is called the minimum heap or small root heap.

Complete Binary Tree

#When it comes to heap sorting, we have to mention complete binary trees. These basic concepts are everywhere on the Internet. I picked the simplest one. .

Complete binary tree: Except for the last level, the number of nodes on each level reaches the maximum; only a few nodes on the right side are missing on the last level.

My own conclusion is that it is precisely because of the following two characteristics,

1. Only the last layer is allowed to have vacant nodes and the vacancies are on the right, that is, the leaf nodes are only Can appear on the two largest levels (regularity of storage method);
2. If i>1, the parent of tree is tree[i p 2] (regularity of its parent and child node values);

makes sorting very convenient.

Heap sort

Heap sort uses the big top heap for ascending order, and the small top heap for descending order.

This example uses the small top heap in descending order to analyze.

Heap sorting steps are as follows:

1. We create an array $arr from the data (49, 38, 65, 97, 76, 13, 27, 50) ;
2. Use the array $arr to create a small top heap (the main steps will be explained in the code comments. The figure below is the process of using an array to create a small top heap);
3. Change the root of the heap ( The smallest element) is exchanged with the last leaf, and the heap length is reduced by one, and jumps to the second step;
4. Repeat steps 2-3 until there is only one node in the heap, and the sorting is completed.

PHP implementation of heap sort

//因为是数组,下标从0开始,所以,下标为n根结点的左子结点为2n+1,右子结点为2n+2;
//初始化值,建立初始堆
$arr=array(49,38,65,97,76,13,27,50);
$arrSize=count($arr);
//将第一次排序抽出来，因为最后一次排序不需要再交换值了。
buildHeap($arr,$arrSize);
for($i=$arrSize-1;$i>0;$i--){
  swap($arr,$i,0);
  $arrSize--;
  buildHeap($arr,$arrSize);
}
//用数组建立最小堆
function buildHeap(&$arr,$arrSize){
  //计算出最开始的下标$index,如图,为数字"97"所在位置,比较每一个子树的父结点和子结点,将最小值存入父结点中
  //从$index处对一个树进行循环比较,形成最小堆
  for($index=intval($arrSize/2)-1; $index>=0; $index--){
    //如果有左节点,将其下标存进最小值$min
    if($index*2+1<$arrSize){
      $min=$index*2+1;
      //如果有右子结点,比较左右结点的大小,如果右子结点更小,将其结点的下标记录进最小值$min
      if($index*2+2<$arrSize){
        if($arr[$index*2+2]<$arr[$min]){
          $min=$index*2+2;
        }
      }
      //将子结点中较小的和父结点比较,若子结点较小,与父结点交换位置,同时更新较小
      if($arr[$min]<$arr[$index]){
        swap($arr,$min,$index);
      }
    }
  }
}
//此函数用来交换下数组$arr中下标为$one和$another的数据
function swap(&$arr,$one,$another){
  $tmp=$arr[$one];
  $arr[$one]=$arr[$another];
  $arr[$another]=$tmp;
}

The following is the final result of sorting:

Related recommendations:

PHPHeap sort algorithmExample analysis

Instance analysis of Heap sort algorithm in Java

PHPHeap sort algorithmExample details

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