Home > Article > Backend Development > PHP heap sorting implementation principle and application method, PHP heap sorting implementation principle_PHP tutorial
PHP heap sorting implementation principle and application method, PHP heap sorting implementation principle_PHP tutorial
- WBOYOriginal
- 2016-07-13 10:10:22783browse
PHP heap sorting implementation principle and application method, PHP heap sorting implementation principle
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
7
2 3 4 6
/
5 9
heapsort($arr);print_r($arr);
After sorting, the standard small top heap structure is generated as follows:
1
3
4 5 6 7
/
8 9
That is, array: array(1,2,3,4,5,6,7,8,9):
Copy code
{
//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 heap sorting will get the maximum number (top of heap, $arr[1]), and repeat the heap adjustment at the root node
swap($arr[$last],$arr[1]);
// Keep the maximum number in the sequence of the number of arrays, define the critical point LAST, so as not to disrupt the sorted elements behind the array when it is sorted.
$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)
{
If(!isset($arr[$l])||$l>$last) return ;
//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]) If($arr[$l]>$arr[$n])
//Exchange the value of the child node ($l) 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.