Heapsort refers to a sorting algorithm designed using a data structure such as a stacked tree (heap). It is a type of selection sort. You can use the characteristics of arrays to quickly locate the element at a specified index. The heap is divided into a large root heap and a small root heap, which is a complete binary tree. The requirement of a large root heap is that the value of each node is not greater than the value of its parent node, that is, A[PARENT[i]] >= A[i]. In non-descending sorting of an array, a large root heap needs to be used, because according to the requirements of a large root heap, the largest value must be at the top of the heap.
Definition of heap
In a complete binary tree, if any parent node is always greater than or equal to (less than or equal to) any child node, it is a big top heap (small top heap).
Heap array storage method
Complete binary trees are suitable for sequential storage, so an array can be regarded as a complete binary tree.
Node numbering: Starting from the root of the tree, from the upper level to the lower level, and from left to right at each level, sequentially number all nodes to obtain a linear sequence that reflects the entire binary tree structure.
Numbering features:
can be determined from the number of a node The node numbers of its parents, left and right children, brothers, etc. are derived. Assume that the node numbered i is ki (1≤i≤n), then:
①If i>1, then the parent number of ki is i/2; if i=1, then Ki is The root node has no parents.
②If 2i≤n, then the number of the left child of Ki is 2i; otherwise, Ki has no left child, that is, Ki must be a leaf. Therefore, the node numbered i>n/2 in the complete binary tree must be a leaf node.
③If 2i+1≤n, then the number of the right child of Ki is 2i+1; otherwise, Ki has no right child.
Note: When ki (0≤i≤n) satisfies the array subscript, the possible left and right children are 2i+1 and 2i+2 respectively.
The idea of heap sorting (taking the big top heap as an example)
Using the feature that the top of the heap records the largest keyword, in each round the top elements of the heap are taken and put into the ordered area. Just like selection sorting selects a maximum value in each round and puts it into the ordered area, heap sorting can be regarded as an improvement of selection sorting.
Construct the initial sequence of keywords to be sorted (R0, R1, R2...Rn) into a large top heap, which is the initial unordered area;
Exchange the top element R[0] with the last element R[n] to obtain a new unordered area (R0, R1, R2,...Rn-1 ) and the new ordered area (Rn);
Since the new top of the heap R[0] after the exchange may violate the nature of the heap, it is necessary to update the current unordered area (R0, R1, R2,...Rn-1) are adjusted to the new heap.
Repeat steps 2 and 3 until the number of elements in the ordered area is n-1, then the entire sorting process is completed.
Algorithm analysis
Filtering algorithm
//The most difficult part to understand
Goal: A complete binary tree in which all subtrees are heaps. This means that the only difference between this binary tree and the node is that it does not satisfy the heap structure. //Very important, very important, very important
As shown below:
Method: First The root is compared with the root nodes of its left and right subtrees, and the largest element is exchanged to the root node; then it is adjusted along the destroyed path until the leaf node, and a new heap is obtained.
Application: 1. In the heap sorting idea mentioned above, in steps 2-3, the unordered area Used when adjusting to heap.
2. Initialize the heap
Initialize the heap
Start from the last non-leaf node i (i=n/2, n is the number of nodes) Initially, the binary tree with i as the root node is adjusted into a heap through filtering. Taking the first picture as an example, the numbering sequence is 8, 7, 6...1.
The correctness of the screening algorithm is guaranteed from the last non-leaf node, because the goal of the screening algorithm is a complete binary tree in which all subtrees are heaps.
php实现堆排序: <?php //堆排序,对简单排序的改进 function swap(array &$arr,$a,$b) { $temp=$arr[$a]; $arr[$a]=$arr[$b]; $arr[$b]=$temp; } //调整$arr[$start]的关键字,$arr[$start]、$arr[$start+1]、、、$arr[$end]成为一个大根堆(根节点最大的完全二叉树) //注意:这里节点s的左右孩子是 2*s +1 和 2*s+2(数组开始下标为0时) function HeapAdjust(array &$arr $start $end) { $temp= $arr[$start]; //沿关键字较大的孩子节点向下筛选 //左右孩子计算 (这里数组的开始下标为0) //左边孩子 2*$start+1,右边孩子 2*$start+2 for ($j=2*$start+1; $j <=$end; $j=2*$j+1) { if ($j !=$end &&$arr[$j] <$arr[$j+1]) { $j++; //转化为右边孩子 } if ($temp >=$arr[$j]) { break; //已经满足大根堆 } //将根节点设置为子节点的较大值 $arr[$start]=$arr[$j]; //继续往下 $start=$j; } $arr[$start] =$temp; } function HeapSort(array &$arr) { $count=count($arr); //先将数据结构造成大根堆 (由于是完全二叉树,所以这里用floor($count/2-1),下标小于或等于这个数的节点都是有孩子的节点) for ($i=floor($count /2)-1; $i >=0 ; $i--) { HeapAdjust($arr,$i,$count); } for ($i=$count-1; $i >=0 ; $i--) { //将堆顶元素与最后一个元素交换,获取到最大元素(交换后的最后一个元素),将最大元素放到数组末尾 swap($arr,0,$i); //经过交换,将最后一个元素(最大元素)脱离大根堆,并将未经排序的新数($arr[0...$i-1])重新调整为大根堆 HeapAdjust($arr,0,$i-1); } } $arr=array(4,1,5,9); HeapSort($arr); v
Related recommendations:
PHP heap sorting implementation code
##Detailed explanation of heap sorting in JavaScript
Detailed explanation of PHP sorting algorithm heap sort
The above is the detailed content of Detailed explanation of php heap sorting. For more information, please follow other related articles on the PHP Chinese website!

PHP is used to build dynamic websites, and its core functions include: 1. Generate dynamic content and generate web pages in real time by connecting with the database; 2. Process user interaction and form submissions, verify inputs and respond to operations; 3. Manage sessions and user authentication to provide a personalized experience; 4. Optimize performance and follow best practices to improve website efficiency and security.

PHP uses MySQLi and PDO extensions to interact in database operations and server-side logic processing, and processes server-side logic through functions such as session management. 1) Use MySQLi or PDO to connect to the database and execute SQL queries. 2) Handle HTTP requests and user status through session management and other functions. 3) Use transactions to ensure the atomicity of database operations. 4) Prevent SQL injection, use exception handling and closing connections for debugging. 5) Optimize performance through indexing and cache, write highly readable code and perform error handling.

Using preprocessing statements and PDO in PHP can effectively prevent SQL injection attacks. 1) Use PDO to connect to the database and set the error mode. 2) Create preprocessing statements through the prepare method and pass data using placeholders and execute methods. 3) Process query results and ensure the security and performance of the code.

PHP and Python have their own advantages and disadvantages, and the choice depends on project needs and personal preferences. 1.PHP is suitable for rapid development and maintenance of large-scale web applications. 2. Python dominates the field of data science and machine learning.

PHP is widely used in e-commerce, content management systems and API development. 1) E-commerce: used for shopping cart function and payment processing. 2) Content management system: used for dynamic content generation and user management. 3) API development: used for RESTful API development and API security. Through performance optimization and best practices, the efficiency and maintainability of PHP applications are improved.

PHP makes it easy to create interactive web content. 1) Dynamically generate content by embedding HTML and display it in real time based on user input or database data. 2) Process form submission and generate dynamic output to ensure that htmlspecialchars is used to prevent XSS. 3) Use MySQL to create a user registration system, and use password_hash and preprocessing statements to enhance security. Mastering these techniques will improve the efficiency of web development.

PHP and Python each have their own advantages, and choose according to project requirements. 1.PHP is suitable for web development, especially for rapid development and maintenance of websites. 2. Python is suitable for data science, machine learning and artificial intelligence, with concise syntax and suitable for beginners.

PHP is still dynamic and still occupies an important position in the field of modern programming. 1) PHP's simplicity and powerful community support make it widely used in web development; 2) Its flexibility and stability make it outstanding in handling web forms, database operations and file processing; 3) PHP is constantly evolving and optimizing, suitable for beginners and experienced developers.


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

EditPlus Chinese cracked version
Small size, syntax highlighting, does not support code prompt function

VSCode Windows 64-bit Download
A free and powerful IDE editor launched by Microsoft

MinGW - Minimalist GNU for Windows
This project is in the process of being migrated to osdn.net/projects/mingw, you can continue to follow us there. MinGW: A native Windows port of the GNU Compiler Collection (GCC), freely distributable import libraries and header files for building native Windows applications; includes extensions to the MSVC runtime to support C99 functionality. All MinGW software can run on 64-bit Windows platforms.

SublimeText3 Linux new version
SublimeText3 Linux latest version

DVWA
Damn Vulnerable Web App (DVWA) is a PHP/MySQL web application that is very vulnerable. Its main goals are to be an aid for security professionals to test their skills and tools in a legal environment, to help web developers better understand the process of securing web applications, and to help teachers/students teach/learn in a classroom environment Web application security. The goal of DVWA is to practice some of the most common web vulnerabilities through a simple and straightforward interface, with varying degrees of difficulty. Please note that this software