The main content of this article is to use PHP to implement heap sorting, which has certain reference value. Interested friends can learn about it.
1. Heap (binary heap): It can be regarded as a complete binary tree. Except for the bottom layer, every level is full, which allows the heap to use arrays. To represent, each node corresponds to an element in the array
2. Given the subscript of a node, the subscript of the parent node and the child node can be calculated Standard; parent(i)=floor(i/2) left(i)=2i right=2i 1
3. Maximum heap and minimum heap, maximum heap: the root node is the maximum value, minimum heap: the root node is the minimum value
4. Heap sorting is to take out the maximum number at the top of the maximum heap, continue to adjust the remaining heap to the maximum heap, and take out the maximum number at the top of the heap again until the remaining Numbers have only one end
5. Maximum heap adjustment (maintain the maximum heap, the child node is always smaller than the parent node); create a maximum heap (adjust an array into an array of the maximum heap); Heap sort (create maximum heap, exchange, maintain maximum heap)
maxHeapify (array,index,heapSize) //最大堆调整 iMax,iLeft,iRight while true iMax=index;iLeft=2*index+1;iRight=2*index+2 如果根结点小于左右子树里结点值,就交换一下这两个值 利用第三方变量,交换下两个值 buildMaxHeap(array) //创建最大堆,把一个数组调整成最大堆的数组 iParent=floor((size-1)/2) for i=iParent;i>=0;i-- maxHeapify (array,i,size) sort(arr) buildMaxHeap(array, heapSize);//创建最大堆 for (int i = heapSize - 1; i > 0; i--) { swap(array, 0, i); //交换第一个和最后一个 maxHeapify(array, 0, i);//维护最大堆,size小了一个
//交换元素 function swap(&$arr,$a,$b){ $temp=$arr[$a]; $arr[$a]=$arr[$b]; $arr[$b]=$temp; } //排序的入口函数 function heapSort(&$arr){ $heapSize=count($arr); buildMaxHeap($arr, $heapSize);//创建最大堆 for ($i = $heapSize - 1; $i > 0; $i--) { swap($arr,0,$i); //交换第一个和最后一个 maxHeapify($arr, 0, $i);//维护最大堆,size小了一个 } } //创建最大堆的函数 function buildMaxHeap(&$arr, $heapSize){ $iParent=floor(($heapSize-1)/2);//根据最后一个元素的索引值计算该结点根结点的索引是哪个 for($i=$iParent;$i>=0;$i--){//这个循环是循环的所有根结点 maxHeapify($arr,$i,$heapSize);//维护最大堆 } } //维护最大堆 function maxHeapify(&$arr,$index,$heapSize){ $iMax=0;$iLeft=0;$iRight=0; while(true){ $iMax=$index; $iLeft=2*$iMax+1; $iRight=2*$iMax+2; if($iLeft<$heapSize && $arr[$iLeft]>$arr[$iMax]){ $iMax=$iLeft; } if($iRight<$heapSize && $arr[$iRight]>$arr[$iMax]){ $iMax=$iRight; } if($iMax!=$index){ swap($arr,$index,$iMax); $index=$iMax; }else{ break; } } } $arr=array(2,1,3,5,9,6); heapSort($arr); var_dump($arr);
Related tutorials: PHP video tutorial
The above is the detailed content of [PHP] Principle and implementation code of heap sorting. For more information, please follow other related articles on the PHP Chinese website!

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

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

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

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

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

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

php判断有没有小数点的方法:1、使用“strpos(数字字符串,'.')”语法,如果返回小数点在字符串中第一次出现的位置,则有小数点;2、使用“strrpos(数字字符串,'.')”语句,如果返回小数点在字符串中最后一次出现的位置,则有。

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


Hot AI Tools

Undresser.AI Undress
AI-powered app for creating realistic nude photos

AI Clothes Remover
Online AI tool for removing clothes from photos.

Undress AI Tool
Undress images for free

Clothoff.io
AI clothes remover

AI Hentai Generator
Generate AI Hentai for free.

Hot Article

Hot Tools

Safe Exam Browser
Safe Exam Browser is a secure browser environment for taking online exams securely. This software turns any computer into a secure workstation. It controls access to any utility and prevents students from using unauthorized resources.

SublimeText3 Linux new version
SublimeText3 Linux latest version

SublimeText3 Chinese version
Chinese version, very easy to use

Notepad++7.3.1
Easy-to-use and free code editor

SublimeText3 Mac version
God-level code editing software (SublimeText3)
