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

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

The code is as follows:

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 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.

http://www.bkjia.com/PHPjc/936800.htmlwww.bkjia.comtruehttp: //www.bkjia.com/PHPjc/936800.htmlTechArticlephp heap sorting implementation principle and application method, php heap sorting implementation principle This article describes the php heap sorting implementation principle and Application method. Share it with everyone for your reference. The specific analysis is as follows:...

Related labels：

php Heap sort method

source：php.cn

Previous article：[PHP Template Engine] Prototype prototype version released! , prototype prototype_PHP tutorial Next article：Follow PSR-4 automatic loading, follow PSR-4 loading_PHP tutorial

Statement of this Website

The content of this article is voluntarily contributed by netizens, and the copyright belongs to the original author. This site does not assume corresponding legal responsibility. If you find any content suspected of plagiarism or infringement, please contact admin@php.cn

Latest Articles by Author

• What is a NullPointerException, and how do I fix it?
  2024-10-22 09:46:29
• From Novice to Coder: Your Journey Begins with C Fundamentals
  2024-10-13 13:53:41
• Unlocking Web Development with PHP: A Beginner's Guide
  2024-10-12 12:15:51
• Demystifying C: A Clear and Simple Path for New Programmers
  2024-10-11 22:47:31
• Unlock Your Coding Potential: C Programming for Absolute Beginners
  2024-10-11 19:36:51
• Unleash Your Inner Programmer: C for Absolute Beginners
  2024-10-11 15:50:41
• Automate Your Life with C: Scripts and Tools for Beginners
  2024-10-11 15:07:41
• PHP Made Easy: Your First Steps in Web Development
  2024-10-11 14:21:21
• Build Anything with Python: A Beginner's Guide to Unleashing Your Creativity
  2024-10-11 12:59:11
• The Key to Coding: Unlocking the Power of Python for Beginners
  2024-10-11 12:17:31

Latest Issues

PHP arrays obtained from URL parameters do not behave as expected I have a URL parameter that contains the category ID and I want to treat it as an array li...

From 2024-04-06 22:09:02

0

1

1428

Where should I place CustomLog directive in apache I'm using php:7.2-apachedocker. I need to disable health check url login access log. Based...

From 2024-04-06 22:03:59

0

1

990

What is the format of the variables in the return value? I am a new learner of php. I found a piece of code: if($x<time()){return[false,'error']...

From 2024-04-06 21:55:20

0

1

778

Problems encountered when using opentbs to generate odt files: values ​​of the same key are displayed in the same row instead of separate columns. I'm using a library called OpenTbs to create odt using PHP, I'm using it because columns a...

From 2024-04-06 20:18:18

0

1

483

Group MySQL results by ID for looping over I have a table with flight data in mysql. I'm writing a php code that will group and displ...

From 2024-04-06 17:27:56

0

1

406

Related Topics

More>

• How to open php file
• How to remove the first few elements of an array in php
• What to do if php deserialization fails
• How to connect php to mssql database
• How to connect php to mssql database
• How to upload html
• How to solve garbled characters in PHP
• How to open php files on mobile phone