The examples in this article describe the implementation principles and application methods of PHP heap sorting. Share it with everyone for your reference. The specific analysis is as follows:
Here, PHP is used as the description language to explain the principle of heap sorting in more detail. To ensure the readability of the program, no optimization is done. Some concepts about the heap in the PHP program are as follows:
Assuming n is the key of the current array, the parent node of n is n>>1 or n/2 (divisible); the left child node of n is l= n<<1 or l=n*2,n The right child node r=(n<<1) 1 or r=l 1
$arr=array(1,8,7,2,3,4,6,5,9);
The original structure of array $arr is as follows:
1
/
8 7
//
2 3 4 6
/
5 9
heapsort($arr);print_r($arr);
The standard small top heap structure generated after sorting is as follows:
1
/
2 3
//
4 5 6 7
/
8 9
That is, array: array(1,2,3,4,5,6,7,8,9):
The code is as follows:
{
//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.
