Detailed explanation of PHP heap sort algorithm example

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 the following

The examples in this article describe Heap sort algorithm implemented in PHP. I would like to share it with you for your reference. The details are as follows:

experience

I have been working for a long time. When I was interviewing the company where I worked, I was shocked by the technical aspect. No, because my knowledge of data structure and other basics is really poor, even though I originally wanted to be a designer. . . However, since I can write PHP just fine, I can come for an internship, but I am still determined to brush up on the basics. In fact, I did feel the importance of basics before. Some deeper things are relatively low-level, and there is no way to proceed without learning them well. For example, I used PHP to make websockets before, which involved concepts such as data packets and data frames. I couldn't figure it out, and I couldn't even process the data, so I had to make up for it later. So I am going to re-learn basic knowledge such as data structures, algorithms, and networks. I would also like to remind everyone, don’t go in the opposite direction like me. It will even be too late until you understand.

Today, let’s talk about the heap sorting question that was asked. When I was asked about it, I even forgot the concept of a complete binary tree. Fortunately, I still have a little bit of data structure foundation, and I understand it somewhat after reading some information, so I want to use PHP to write a heap sort of binary trees, and by the way, I also review binary trees, heaps and other data structures.

Heap

Heap is a general term for a special type of data structure in computer science. It is usually a data structure that can be Seen as an array object of a tree.

Heap{k1,k2,ki,…,kn} (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 or 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 layer, the number of nodes on each layer reaches the maximum; only a few nodes on the right are missing on the last layer.

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:

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