Detailed explanation of php heap sorting

Heapsort refers to a sorting algorithm designed using a data structure such as a stacked tree (heap). It is a type of selection sort. You can use the characteristics of arrays to quickly locate the element at a specified index. The heap is divided into a large root heap and a small root heap, which is a complete binary tree. The requirement of a large root heap is that the value of each node is not greater than the value of its parent node, that is, A[PARENT[i]] >= A[i]. In non-descending sorting of an array, a large root heap needs to be used, because according to the requirements of a large root heap, the largest value must be at the top of the heap.

Definition of heap

In a complete binary tree, if any parent node is always greater than or equal to (less than or equal to) any child node, it is a big top heap (small top heap).

Heap array storage method

Complete binary trees are suitable for sequential storage, so an array can be regarded as a complete binary tree.

• Node numbering: Starting from the root of the tree, from the upper level to the lower level, and from left to right at each level, sequentially number all nodes to obtain a linear sequence that reflects the entire binary tree structure.

• Numbering features:

can be determined from the number of a node The node numbers of its parents, left and right children, brothers, etc. are derived. Assume that the node numbered i is ki (1≤i≤n), then:

　①If i>1, then the parent number of ki is i/2; if i=1, then Ki is The root node has no parents.

　②If 2i≤n, then the number of the left child of Ki is 2i; otherwise, Ki has no left child, that is, Ki must be a leaf. Therefore, the node numbered i>n/2 in the complete binary tree must be a leaf node.

　③If 2i+1≤n, then the number of the right child of Ki is 2i+1; otherwise, Ki has no right child.

Note: When ki (0≤i≤n) satisfies the array subscript, the possible left and right children are 2i+1 and 2i+2 respectively.

The idea of ​​heap sorting (taking the big top heap as an example)

Using the feature that the top of the heap records the largest keyword, in each round the top elements of the heap are taken and put into the ordered area. Just like selection sorting selects a maximum value in each round and puts it into the ordered area, heap sorting can be regarded as an improvement of selection sorting.

1. Construct the initial sequence of keywords to be sorted (R0, R1, R2...Rn) into a large top heap, which is the initial unordered area;

2. Exchange the top element R[0] with the last element R[n] to obtain a new unordered area (R0, R1, R2,...Rn-1 ) and the new ordered area (Rn);

3. Since the new top of the heap R[0] after the exchange may violate the nature of the heap, it is necessary to update the current unordered area (R0, R1, R2,...Rn-1) are adjusted to the new heap.

Repeat steps 2 and 3 until the number of elements in the ordered area is n-1, then the entire sorting process is completed.

Algorithm analysis

Filtering algorithm

//The most difficult part to understand

• Goal: A complete binary tree in which all subtrees are heaps. This means that the only difference between this binary tree and the node is that it does not satisfy the heap structure. //Very important, very important, very important

As shown below:

• Method: First The root is compared with the root nodes of its left and right subtrees, and the largest element is exchanged to the root node; then it is adjusted along the destroyed path until the leaf node, and a new heap is obtained.

• Application: 1. In the heap sorting idea mentioned above, in steps 2-3, the unordered area Used when adjusting to heap.

2. Initialize the heap

Initialize the heap

Start from the last non-leaf node i (i=n/2, n is the number of nodes) Initially, the binary tree with i as the root node is adjusted into a heap through filtering. Taking the first picture as an example, the numbering sequence is 8, 7, 6...1.

The correctness of the screening algorithm is guaranteed from the last non-leaf node, because the goal of the screening algorithm is a complete binary tree in which all subtrees are heaps.

php实现堆排序：
<?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(4,1,5,9);
   HeapSort($arr);
   v

Related recommendations:

PHP heap sorting implementation code

##Detailed explanation of heap sorting in JavaScript

Detailed explanation of PHP sorting algorithm heap sort

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