## current position：Home>JavaScript algorithm -- heap sorting

# JavaScript algorithm -- heap sorting

2022-04-29 18:27:38【Zhuge Hanxin】

## One 、 Knowledge preparation

** The first is the concept of heap .** The pile here can be simply understood as a pyramid shaped image . We use binary trees to construct , But our binary tree is complete , That is, the expansion of the tree should be arranged in order .

- The heap is a complete binary tree .
- Perfect binary tree ： Binary tree except the last layer , The number of other stratification points reaches the maximum , All nodes of the last layer are concentrated on the left （ When the left nodes are full , The node can only be missing on the right ）.
- Big pile top ： The root node is the maximum , The value of each node is greater than or equal to the value of its child node .
- Small cap pile ： The root node is the minimum , The value of each node is less than or equal to the value of its child node .
- Heap storage ： The heap is implemented by an array , It is equivalent to traversing the binary tree .

Pile top ：

Small pile top ：

## Two 、 Sorting ideas

- Convert the initial binary tree into a large top heap （heapify）（ The essence is to start from the first non leaf node , From bottom to top , right to left , Do... For each non leaf node heapify operation ）, At this time, the root node is the maximum , Exchange it with the last node .
- Except for the last node , Convert the new heap composed of other nodes into a large top heap （ In essence, it is to do... On the root node heapify operation ）, At this time, the root node is the next maximum , Exchange it with the last node .
- Repeat step 2, Until the number of elements in the heap is 1（ Or the length of its corresponding array is 1）, Sort complete .

## 3、 ... and 、 Dynamic diagram demonstration

Moving graph 1：

Moving graph 2：

## Four 、JS Code implementation

```
**// Swap two nodes
function swap(A, i, j) {
let temp = A[i];
A[i] = A[j];
A[j] = temp;
}
// take i The pile below the node is sorted into a large top pile , Note that the foundation of this step is actually ：
// hypothesis node i The following sub pile is already a large top pile ,shiftDown Functionally implemented
// The function is actually ： find node i In the include node i The right position in the pile . Back
// Will write a for loop , Start with the first non leaf node , For every non leaf node
// All implemented shiftDown operation , So it satisfies the node i The following sub heap is already a big one
// Top pile
function shiftDown(A, i, length) {
let temp = A[i]; // Current parent node
// j<length The purpose of is to i The following nodes are all adjusted in order
for(let j = 2*i+1; j < length; j = 2*j+1) {
temp = A[i]; // take A[i] Take out , The whole process is equivalent to finding A[i] Where to be
if(j+1 < length && A[j] < A[j+1]) {
j++; // Find the older of the two children , Compare it with the parent node
}
if(temp < A[j]) {
swap(A, i, j) // If the parent is smaller than the child : In exchange for ; Otherwise jump out
i = j; // After exchanging ,temp The subscript of becomes j
} else {
break;
}
}
}
// Heap sort
function heapSort(A) {
// Initializing the big top heap , Start with the first non leaf node
for(let i = Math.floor(A.length/2-1); i >= 0; i--) {
shiftDown(A, i, A.length);
}
// Sort , every time for Loop to find a current maximum , Array length minus one
for(let i = Math.floor(A.length-1); i > 0; i--) {
swap(A, 0, i); // The root node exchanges with the last node
shiftDown(A, 0, i); // Adjust from root , And the last node is already when
// Front maximum , There's no need to compare , So the third parameter
// by i, That is, to compare to the previous node of the last node
}
}
let Arr = [3, 6, 13, 8, 2];
heapSort(Arr);
console.log(Arr); // [2, 3, 6, 8, 13]
```

The code looks complex . In fact, we only need to remember two points ：

1、 The array facing the heap sort is unordered at first , This is the time , We need to build a sort top in the rule （ The maximum or minimum of all ）; So that's the first loop you need to do in the code , as follows ：

```
// Initializing the big top heap , Start with the first non leaf node
for(let i = Math.floor(A.length/2-1); i >= 0; i--) {
shiftDown(A, i, A.length);
}
```

Cycle completion , We can get the following data ：

```
[13, 8, 3, 6, 2]
```

The number above is the data after the first time of our cycle , You can know , Put them into the whole binary tree in turn , The parent node is always the largest one .

Then we just need to continue the cycle .

2、 Through the first cycle , The whole complete binary tree has been constructed , But the data has not been sorted yet , All we need to do is put this binary tree , Repeat method 1 , Sort . That's why there's a second cycle , as follows ：

```
// Sort , every time for Loop to find a current maximum , Array length minus one
for(let i = Math.floor(A.length-1); i > 0; i--) {
swap(A, 0, i); // The root node exchanges with the last node
shiftDown(A, 0, i); // Adjust from root , And the last node is already when
// Front maximum , There's no need to compare , So the third parameter
// by i, That is, to compare to the previous node of the last node
}
```

## 5、 ... and 、 Assist in understanding the case

** step 1**

Initializing the big top heap , First select the last non leaf node ( We just need to adjust the size relationship between the parent node and the child node , The size relationship between leaf nodes does not need to be adjusted ). Set the array to arr, Then the subscript of the first non leaf node is ：i = Math.floor(arr.length/2 - 1) = 1, That's numbers 4, As shown in the dotted line box , Find the maximum of three numbers , Exchange with the parent node .

then , Subscript i Decrease in turn 1（ That is, start from the first non leaf node , right to left , Traverse all non leaf nodes from bottom to top ）. This is true for every subsequent adjustment ： Find the maximum value in the parent-child node , exchange .

The number in this step 6、1 After exchanging , Numbers [1,5,4] The composition of the heap is out of order , One step adjustment is needed . So pay attention to , After adjusting one non leaf node at a time , We should observe whether it will affect the sub heap order ！

After this adjustment , The root node is the maximum , Formed a large top pile , Exchange the root node with the last node .

** Step two **

Except for the current last node 6( That is, the maximum value ), Add the remaining nodes [4,5,3,1] Form a new reactor and convert it into a large top reactor ( observe , At this time, other nodes other than the root node , All meet the characteristics of large top pile , So you can start from the root node 4 Began to adjust , Find out 4 It should be in the right position ).** step 3**

Next, repeat step 2, Until the number of elements in the heap is 1：

The number of elements in the heap is 1, Sort complete .

reference ：

Ten classic sorting algorithm animations , Just look at me ！

JS Implement heap sort

js Heap sort algorithm

Javascript Algorithm —— Heap sort

copyright notice

author[Zhuge Hanxin],Please bring the original link to reprint, thank you.

https://en.qdmana.com/2022/119/202204291657165200.html

## The sidebar is recommended

- About node JS server related concepts
- Access control module (2)
- About virtual lists
- Developing figma plug-in using Vue 3 + vite
- Learn more about the garbage collection engine of chrome V8 JavaScript engine
- Vue3 uses vite instead of webpack
- How to upload applet code through node? Just take a look
- Using H5 video tag in Vue to play local video in pop-up window
- What is the difference between classes in Es5 and ES6?
- [Vue] play with the slot

## guess what you like

[Part 4 of front-end deployment] using docker to build cache and multi-stage construction to optimize single page applications

Vue2 simple use of vant (based on Vue CLI)

node. JS server

React uses concurrent mode. When the rendering phase exceeds the time slice, high priority tasks jump the queue. How will the lanes on the fiber of the previous task be solved

Vuecli2 multi page, how to remove HTML suffix

Vue router dynamically modifies routing parameters

How to use webpack or configure quasar after context isolation is turned on by electron?

Vue3 how do parent components call child component methods

Es learning notes (I): http request

【Java WEB】AJAX

## Random recommended

- Java project: nursing home management system (java + springboot + thymeleaf + HTML + JS + MySQL)
- Java project: drug management system (java + springboot + HTML + layui + bootstrap + seals + MySQL)
- Java project: agricultural material management system (java + springboot + easyUI + HTML + Maven + MySQL)
- How do Vue, native JS and jQuery feel about development
- The Ajax backend accepts post data and writes it directly to the database
- Java project: agricultural material management system (java + springboot + easyUI + HTML + Maven + MySQL)
- Brother Lao Yu takes you to play with esp32:14 and personally make a two-way wireless remote control (I)
- How to create JavaScript custom events
- A king's time, I learned nginx
- Vue quick start (with actual small items: Notepad, weather forecast, music player)
- Vue: convert user input to numeric type
- - Status code: 404 for http://mirrors.cloud.aliyuncs.com/centos/8/AppStream/x86_64/os/repodata/repom
- vue. config. Understanding of agent in JS
- After the node is successfully installed, CMD can be executed, but the compiler webstorm runs NPM install and prompts that there is no solution to this command
- How to develop and deploy front-end code in large companies
- Vue assigns permissions to buttons through instructions
- [development diary from 22 years to April] Vue problems encountered in actual projects and their solutions
- [methodology 1] CSS development skills - global style setting and local style
- vue3. 0 dynamically bind and obtain DOM through ref;
- How to use HTML to display segmentation
- How to use HTML for touch event in mobile terminal
- How to define and use HTML box model
- How to use the box pack attribute and box align attribute inside the box in HTML
- What are the differences and relationships among HTML, CSS and JS
- How to save home page as HTML
- How to solve the post request return 405 of nginx reverse proxy to HTML page
- How to upload pictures without refresh with HTML5 + PHP
- How to define HTML text tags, pictures, paths, hyperlinks and anchors
- How to upload static HTML files to the host or server
- How to use calculated and watch in Vue
- How does Vue Preview PDF, word, xls, PPT and txt files
- Can jQuery listen for events
- Luxury cars "senseless price increase", the configuration of the new Porsche Macan remains unchanged, with a maximum increase of 19000 yuan
- 1-ch579m program upgrade OTA (self built Internet of things platform) - ch579m uses its own Ethernet to remotely download and upgrade MCU program through HTTP (MCU program rotation check and update)
- The front-end downloads files, and the back-end sends gzip files. Is there a way to get the file size?
- Why does Vue route jump refresh the page?
- The conversion code of Babel in the project needs to include node_ Modules
- [nginx] prefix removal in nginx proxy pass configuration
- Vue packaging error module build failed: typeerror: this getOptions is not a function
- Use of I18N in Vue