search
HomeBackend DevelopmentPHP TutorialPHP heap sorting implementation principle and application method_PHP tutorial
PHP heap sorting implementation principle and application method_PHP tutorialJul 13, 2016 am 09:59 AM
phpandmainprincipleheapaccomplishapplicationsortarticlemethod

PHP heap sorting implementation principles and application methods

This article mainly introduces the PHP heap sorting implementation principles and application methods, and analyzes the principles and usage techniques of heap sorting in more detail , has certain reference value, friends in need can refer to it

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

$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:

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

www.bkjia.comtruehttp: //www.bkjia.com/PHPjc/975889.htmlTechArticlephp heap sorting implementation principle and application method This article mainly introduces php heap sorting implementation principle and application method, which is more Detailed analysis of the principles and usage techniques of heap sorting, with certain reference...
Statement
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
php怎么把负数转为正整数php怎么把负数转为正整数Apr 19, 2022 pm 08:59 PM

php把负数转为正整数的方法:1、使用abs()函数将负数转为正数,使用intval()函数对正数取整,转为正整数,语法“intval(abs($number))”;2、利用“~”位运算符将负数取反加一,语法“~$number + 1”。

php怎么实现几秒后执行一个函数php怎么实现几秒后执行一个函数Apr 24, 2022 pm 01:12 PM

实现方法:1、使用“sleep(延迟秒数)”语句,可延迟执行函数若干秒;2、使用“time_nanosleep(延迟秒数,延迟纳秒数)”语句,可延迟执行函数若干秒和纳秒;3、使用“time_sleep_until(time()+7)”语句。

php怎么除以100保留两位小数php怎么除以100保留两位小数Apr 22, 2022 pm 06:23 PM

php除以100保留两位小数的方法:1、利用“/”运算符进行除法运算,语法“数值 / 100”;2、使用“number_format(除法结果, 2)”或“sprintf("%.2f",除法结果)”语句进行四舍五入的处理值,并保留两位小数。

php字符串有没有下标php字符串有没有下标Apr 24, 2022 am 11:49 AM

php字符串有下标。在PHP中,下标不仅可以应用于数组和对象,还可应用于字符串,利用字符串的下标和中括号“[]”可以访问指定索引位置的字符,并对该字符进行读写,语法“字符串名[下标值]”;字符串的下标值(索引值)只能是整数类型,起始值为0。

php怎么根据年月日判断是一年的第几天php怎么根据年月日判断是一年的第几天Apr 22, 2022 pm 05:02 PM

判断方法:1、使用“strtotime("年-月-日")”语句将给定的年月日转换为时间戳格式;2、用“date("z",时间戳)+1”语句计算指定时间戳是一年的第几天。date()返回的天数是从0开始计算的,因此真实天数需要在此基础上加1。

php怎么读取字符串后几个字符php怎么读取字符串后几个字符Apr 22, 2022 pm 08:31 PM

在php中,可以使用substr()函数来读取字符串后几个字符,只需要将该函数的第二个参数设置为负值,第三个参数省略即可;语法为“substr(字符串,-n)”,表示读取从字符串结尾处向前数第n个字符开始,直到字符串结尾的全部字符。

php怎么替换nbsp空格符php怎么替换nbsp空格符Apr 24, 2022 pm 02:55 PM

方法:1、用“str_replace(" ","其他字符",$str)”语句,可将nbsp符替换为其他字符;2、用“preg_replace("/(\s|\&nbsp\;||\xc2\xa0)/","其他字符",$str)”语句。

php怎么查找字符串是第几位php怎么查找字符串是第几位Apr 22, 2022 pm 06:48 PM

查找方法:1、用strpos(),语法“strpos("字符串值","查找子串")+1”;2、用stripos(),语法“strpos("字符串值","查找子串")+1”。因为字符串是从0开始计数的,因此两个函数获取的位置需要进行加1处理。

See all articles

Hot AI Tools

Undresser.AI Undress

Undresser.AI Undress

AI-powered app for creating realistic nude photos

AI Clothes Remover

AI Clothes Remover

Online AI tool for removing clothes from photos.

Undress AI Tool

Undress AI Tool

Undress images for free

Clothoff.io

Clothoff.io

AI clothes remover

AI Hentai Generator

AI Hentai Generator

Generate AI Hentai for free.

Hot Tools

EditPlus Chinese cracked version

EditPlus Chinese cracked version

Small size, syntax highlighting, does not support code prompt function

VSCode Windows 64-bit Download

VSCode Windows 64-bit Download

A free and powerful IDE editor launched by Microsoft

ZendStudio 13.5.1 Mac

ZendStudio 13.5.1 Mac

Powerful PHP integrated development environment

MantisBT

MantisBT

Mantis is an easy-to-deploy web-based defect tracking tool designed to aid in product defect tracking. It requires PHP, MySQL and a web server. Check out our demo and hosting services.

SublimeText3 Chinese version

SublimeText3 Chinese version

Chinese version, very easy to use