PHP heap sorting implementation principle and application method_PHP tutorial

function heapsort(&$arr)
{
//Find the last element position
$last=count($arr);
//$arr[0]
is usually ignored in heap sorting array_unshift($arr,0);
//The last non-leaf node
$i=$last>>1;

//Organize into a large top heap, move the largest number to the top of the heap, exchange the maximum number with the tail of the heap, and ignore the maximum number at the back end of the array (last) in subsequent calculations until the top of the heap (last=top of the heap)
while(true)
{
adjustnode($i,$last,$arr);
if($i>1)
{
//Move the node pointer and traverse all non-leaf nodes
$i--;
}
else
{
//Critical point last=1, that is, all sorting is completed
if($last==1)break;
//When i is 1, it means that each time the heap is sorted, the maximum number (top of the heap, $arr[1]) will be obtained, and the heap is repeatedly adjusted at the root node
swap($arr[$last],$arr[1]);
//Reserve the maximum number in order of size at the end of the array, and define the critical point last to avoid re-disrupting the sorted elements behind the array when sorting the heap
$last--;
}
}
//Pop the first array element
array_shift($arr);
}

//Organize the current tree nodes ($n), after the critical point $last are the sorted elements
function adjustnode($n,$last,&$arr)
{
$l=$n<<1; //The left child of $n
if(!isset($arr[$l])||$l>$last) return ;
$r=$l 1; //Right child bit of $n

//If the right child is larger than the left child, let the right child of the parent node be larger than
if($r<=$last&&$arr[$r]>$arr[$l]) $l=$r;
//If the child node $l is larger than the parent node $n, exchange it with the parent node $n
if($arr[$l]>$arr[$n])
{
//The value of the child node ($l) is exchanged with the value of the parent node ($n)
swap($arr[$l],$arr[$n]);
//After the exchange, the value ($arr[$n]) of the parent node ($n) may still be smaller than the value of the child node of the atomic node ($l), so the child nodes of the atomic node ($l) need to be adjusted. , implemented using recursion
adjustnode($l,$last,$arr);
}
}

//Exchange two values ​​
function swap(&$a,&$b)
{
$a=$a ^ $b;
$b=$a ^ $b;
$a=$a ^ $b;
}

I hope this article will be helpful to everyone’s PHP programming design.