Implementation of heap sorting principle based on PHP

Heap

Heap is the general 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), (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 the complete binary tree. These basic concepts are everywhere on the Internet. I picked the simplest one. of. .

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 side are missing on the last layer.

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

• Only the last layer is allowed to have vacant nodes and the vacancies are on the right, that is, leaf nodes can only be on Appears on the two largest levels (regularity of storage methods);
• 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 , exchange the root of the heap (the smallest element) with the last leaf, reduce the length of the heap by one, and jump to the second step;

4. Repeat steps 2-3 until there is only one node in the heap , 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 the sort:

Heap is used for full sorting, the time complexity is O(nlogn)

And quick sort is used for full sorting, the average time complexity is also O( nlogn)

But when heap sorting can be used to find TopK, the time complexity of the heap is O(Klog2(n), because it only requires K rounds of sorting.

Recommended tutorial ：《

PHP》

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