PHP heap sort implementation principle and application code

PHP heap sort implementation principle and application code_PHP tutorial

WBOY

Release： 2016-07-20 11:08:01

Original

845 people have browsed it

php tutorial heap sorting implementation principle and application code
author: lajabs
email: agl0dhlvqgdtywlslmnvbq==

This article uses PHP as the description language to explain the principle of heap sorting in more detail
Due to the guarantee The program is readable, so no optimization is done.

Some concepts about the heap in the PHP program:
Assume n is the key of the current array, then
n’s parent node is n>> ;1 or n/2 (divisible);
n’s left child node l= n<<1 or l=n*2, n’s right child node r=(n<<1)+1 or r =l+1
*/
$arr=array(1,8,7,2,3,4,6,5,9);
/*
The original form of array $arr The structure is as follows:
1
8 7
2 3 4 6
/
5 9

*/

heaps tutorial ort($arr);

print_r($arr);
/*
The standard small top heap structure generated after sorting is as follows:
1
2 / 3
/ */

function heapsort(&$arr)
{
//Find the last element position
$last=count($arr);
//Usually in heap sorting Ignore $arr[0]

array_unshift($arr,0);

//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 heap)
while(true)
{
adjustnode($i,$last,$arr);
if($i>1)
{
Poems, traversed all non-leaf nodes
$ i-;
}
Else
{
// Treasure point LAST = 1, all sorted
if ($ last = = 1) BREAK;
// When I is 1, it means that each pile of each pile will get the maximum number (pile top, $ arr [1]), repeat the heap at the root node
SWAP ($ arrR [$ Last], $ arr [1]);
// The maximum number of the size is retained at the end of the array, defining the critical point LAST, so as not to disrupt the elements that have been sorted after the array when they are sorted. last--;
; n), after the critical point $last is the sorted element
function adjustnode($n,$last,&$arr)
{
$l=$n< The left child of n
if(!isset($arr[$l])||$l>$last) return ;
$r=$l+1; //The right child of $n

//If the right child is larger than the left child, then let the right child of the parent node be larger than 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)

//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. , use recursion to implement

adjustnode($l,$last,$arr);
}
}

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