Shulou(Shulou.com)06/01 Report--

This article mainly shows you "how to achieve heap sorting in web development", the content is easy to understand, clear, hope to help you solve your doubts, let the editor lead you to study and learn "how to achieve heap sorting in web development" this article.

Preliminary knowledge: heap structure

Heap is a complete binary tree with the following properties: the value of each node is greater than or equal to the value of its left and right child nodes, which is called large top heap, or the value of each node is less than or equal to the value of its left and right child nodes, which is called small top heap.

Heap sort

Heap sorting (Heapsort) is a sort algorithm designed by using the data structure of heap (the later [graphical data structure] will explain the analysis). Stacking is a structure similar to a complete binary tree and satisfies the property of stacking at the same time, that is, the key value or index of a child node is always less than (or greater than) its parent node. Heap sorting can be said to be a selective sort that uses the concept of heap to sort. There are two methods:

Large top heap: the value of each node is greater than or equal to the value of its child node, used in ascending order in the heap sorting algorithm

Small top heap: the value of each node is less than or equal to the value of its child node, used in descending order in the heap sorting algorithm

The average time complexity of heap sorting is nlogn.

Algorithm step

Create a heap H [0... NMur1]

Swap head (maximum) and tail of the heap

Reduce the heap size by 1 and call shift_down (0) to adjust the data at the top of the new array to the appropriate location

Repeat step 2 until the heap size is 1.

Source: https://github.com/hustcc/JS-Sorting-Algorithm

Algorithm demonstration

Process interpretation of sorting animation

First, store all the numbers in the heap

Build the heap according to the big top heap, one of the characteristics of the big top heap is that the data will be taken out from large to small, the extracted numbers will be arranged in the opposite order, and the numbers will be sorted.

Here, the number 5 enters the heap first.

The number 2 is on the heap

The number 7 is on the heap, and 7 is the last node at this time, compared with the last non-leaf node (that is, the number 5). Because 7 is greater than 5, 7 and 5 interact.

According to the above operation, put all the numbers into the heap, and then adjust from left to right and from top to bottom to construct a large top heap.

After entering the heap, take out the top element of the heap, place the last element on the top of the heap, and restructure it to meet the definition of the heap.

The number 7 of the element at the top of the heap is taken out, and the number 4 at the end of the element is placed at the top of the heap. in order to maintain the definition of the large top stack, the last non-leaf node number 5 is compared with 4, and then the positions of the two numbers are exchanged

Repeat the adjustment + exchange steps until the whole sequence is in order

Code implementation

In order to better let readers use their familiar programming language to understand animation, the author will post the reference code of a variety of programming languages, all from the Internet.

Go code implementation

Java code implementation

Python code implementation

JavaScript code implementation

These are all the contents of the article "how to implement heap sorting in web development". Thank you for reading! I believe we all have a certain understanding, hope to share the content to help you, if you want to learn more knowledge, welcome to follow the industry information channel!

Welcome to subscribe "Shulou Technology Information " to get latest news, interesting things and hot topics in the IT industry, and controls the hottest and latest Internet news, technology news and IT industry trends.