


Detailed graphic explanation of Heap Sort heap sorting algorithm and JavaScript code implementation_Basic knowledge
1. I have to talk about binary trees
To understand the heap, you must first understand the binary tree. In computer science, a binary tree is a tree structure in which each node has at most two subtrees. Usually subtrees are called "left subtree" and "right subtree". Binary trees are often used to implement binary search trees and binary heaps.
Each node of a binary tree has at most two subtrees (there are no nodes with degree greater than 2). The subtrees of a binary tree are divided into left and right subtrees, and the order cannot be reversed. The i-th level of a binary tree has at most 2i - 1 nodes; a binary tree with depth k has at most 2k - 1 nodes; for any binary tree T, if the number of terminal nodes is n0, the number of nodes with degree 2 is n2, then n0 = n2 + 1.
Three main differences between trees and binary trees:
The number of nodes of a tree must be at least 1, while the number of nodes of a binary tree can be 0
There is no limit to the maximum degree of a node in a tree, while the maximum degree of a node in a binary tree is 2
The nodes of the tree are not divided into left and right, while the nodes of the binary tree are divided into left and right
Binary trees are divided into complete binary trees and full binary trees
Full binary tree: A tree with depth k and 2k - 1 nodes is called a full binary tree
(full binary tree with depth 3)
Complete binary tree: A binary tree with depth k and n nodes. If and only if each of its nodes corresponds to the nodes numbered 1 to n in the full binary tree with depth k, it is called a complete binary tree
(complete binary tree with depth 3)
2. What is a heap?
A heap (binary heap) can be regarded as a complete binary tree. An "excellent" property of a complete binary tree is that every level except the lowest level is full, which allows the heap to use arrays to Represented (ordinary binary trees are usually represented by linked lists as basic containers), each node corresponds to an element in the array.
As shown below, it is the relationship between a heap and an array
(Interrelationship between heap and array)
For a given subscript i of a node, the subscripts of the parent node and child node of this node can be easily calculated:
Parent(i) = floor(i/2), i’s parent node subscript
Left(i) = 2i, the subscript of the left child node of i
Right(i) = 2i + 1, i’s right child node subscript
Binary heaps are generally divided into two types: maximum heap and minimum heap.
Maximum heap:
The maximum element value in the max heap appears at the root node (top of the heap)
The element value of each parent node in the heap is greater than or equal to its child node (if it exists)
(maximum heap)
Minimum heap:
The smallest element value in the min-heap appears at the root node (top of the heap)
The element value of each parent node in the heap is less than or equal to its child node (if it exists)
(min heap)
3. Heap sorting principle
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. This process continues until there is only one remaining number. Define the following operations on the heap:
Max-Heapify: Adjust the end child nodes of the heap so that the child nodes are always smaller than the parent node
Create a maximum heap (Build-Max-Heap): Reorder all data in the heap to make it a maximum heap
Heap-Sort: Remove the root node of the first data and perform a recursive operation of maximum heap adjustment
Before continuing with the following discussion, one thing that needs to be noted is that arrays are all Zero-Based, which means that our heap data structure model will change
(Zero-Based)
Correspondingly, several calculation formulas must also be adjusted accordingly:
Parent(i) = floor((i-1)/2), i’s parent node subscript
Left(i) = 2i + 1, i’s left child node subscript
Right(i) = 2(i + 1), i’s right child node subscript
The function of maximum heap adjustment (MAX-HEAPIFY) is to maintain the properties of the maximum heap and is the core subroutine for creating the maximum heap. The function process is as shown in the figure:
(Max-Heapify)
Since after one adjustment, the heap still violates the heap properties, recursive testing is required to make the entire heap satisfy the heap properties. This can be expressed in JavaScript as follows:
/** * 从 index 开始检查并保持最大堆性质 * * @array * * @index 检查的起始下标 * * @heapSize 堆大小 * **/ function maxHeapify(array, index, heapSize) { var iMax = index, iLeft = 2 * index + 1, iRight = 2 * (index + 1); if (iLeft < heapSize && array[index] < array[iLeft]) { iMax = iLeft; } if (iRight < heapSize && array[iMax] < array[iRight]) { iMax = iRight; } if (iMax != index) { swap(array, iMax, index); maxHeapify(array, iMax, heapSize); // 递归调整 } } function swap(array, i, j) { var temp = array[i]; array[i] = array[j]; array[j] = temp; }
Generally speaking, recursion is mainly used in the divide and conquer method, but divide and conquer is not required here. Moreover, recursive calls require pushing/clearing the stack, which has a slight performance disadvantage compared with iteration. Of course, following the 20/80 rule, this can be ignored. But if you feel that using recursion will make you feel uncomfortable, you can also use iteration, such as the following:
/** * 从 index 开始检查并保持最大堆性质 * * @array * * @index 检查的起始下标 * * @heapSize 堆大小 * **/ function maxHeapify(array, index, heapSize) { var iMax, iLeft, iRight; while (true) { iMax = index; iLeft = 2 * index + 1; iRight = 2 * (index + 1); if (iLeft < heapSize && array[index] < array[iLeft]) { iMax = iLeft; } if (iRight < heapSize && array[iMax] < array[iRight]) { iMax = iRight; } if (iMax != index) { swap(array, iMax, index); index = iMax; } else { break; } } } function swap(array, i, j) { var temp = array[i]; array[i] = array[j]; array[j] = temp; }
The function of creating a maximum heap (Build-Max-Heap) is to transform an array into a maximum heap. It accepts two parameters: array and heap size. Build-Max-Heap will call Max-Heapify from bottom to top. Transform the array and create a maximum heap. Because Max-Heapify can ensure that the nodes after the node with subscript i satisfy the maximum heap property, bottom-up calling Max-Heapify can maintain this property during the transformation process. If the number of elements in the maximum heap is n, then Build-Max-Heap starts from Parent(n) and calls Max-Heapify upwards. The process is as follows:
Described in JavaScript as follows:
function buildMaxHeap(array, heapSize) { var i, iParent = Math.floor((heapSize - 1) / 2); for (i = iParent; i >= 0; i--) { maxHeapify(array, i, heapSize); } }
Heap-Sort is the interface algorithm of heap sort. Heap-Sort first calls Build-Max-Heap to transform the array into a maximum heap, then exchanges the top and bottom elements of the heap, then raises the bottom, and finally Recall Max-Heapify to maintain the maximum heap properties. Since the top element of the heap must be the largest element in the heap, after one operation, the largest element existing in the heap is separated from the heap. After repeating n-1 times, the array is arranged. The whole process is as follows:
Described in JavaScript as follows:
function heapSort(array, heapSize) { buildMaxHeap(array, heapSize); for (int i = heapSize - 1; i > 0; i--) { swap(array, 0, i); maxHeapify(array, 0, i); } }
4.JavaScript language implementation
Finally, organize the above into the complete javascript code as follows:
function heapSort(array) { function swap(array, i, j) { var temp = array[i]; array[i] = array[j]; array[j] = temp; } function maxHeapify(array, index, heapSize) { var iMax, iLeft, iRight; while (true) { iMax = index; iLeft = 2 * index + 1; iRight = 2 * (index + 1); if (iLeft < heapSize && array[index] < array[iLeft]) { iMax = iLeft; } if (iRight < heapSize && array[iMax] < array[iRight]) { iMax = iRight; } if (iMax != index) { swap(array, iMax, index); index = iMax; } else { break; } } } function buildMaxHeap(array) { var i, iParent = Math.floor(array.length / 2) - 1; for (i = iParent; i >= 0; i--) { maxHeapify(array, i, array.length); } } function sort(array) { buildMaxHeap(array); for (var i = array.length - 1; i > 0; i--) { swap(array, 0, i); maxHeapify(array, 0, i); } return array; } return sort(array); }
5. Application of heap sort algorithm
(1) Algorithm performance/complexity
The time complexity of heap sort is very stable (we can see that it is not sensitive to the input data), and is O(n㏒n) complexity. The best case is the same as the worst case.
However, its space complexity varies from implementation to implementation. Two common complexities have been discussed above: O(n) and O(1). In line with the principle of saving space, I recommend the O(1) complexity method.
(2) Algorithm stability
Heap sorting involves a large number of screening and moving processes and is an unstable sorting algorithm.
(3) Algorithm applicable scenarios
Heap sorting will cause relatively large overhead in the process of establishing and adjusting the heap, and is not suitable when there are few elements. However, it is still a good choice when there are many elements. Especially when solving problems such as "the first n largest numbers", it is almost the preferred algorithm.

Python and JavaScript have their own advantages and disadvantages in terms of community, libraries and resources. 1) The Python community is friendly and suitable for beginners, but the front-end development resources are not as rich as JavaScript. 2) Python is powerful in data science and machine learning libraries, while JavaScript is better in front-end development libraries and frameworks. 3) Both have rich learning resources, but Python is suitable for starting with official documents, while JavaScript is better with MDNWebDocs. The choice should be based on project needs and personal interests.

The shift from C/C to JavaScript requires adapting to dynamic typing, garbage collection and asynchronous programming. 1) C/C is a statically typed language that requires manual memory management, while JavaScript is dynamically typed and garbage collection is automatically processed. 2) C/C needs to be compiled into machine code, while JavaScript is an interpreted language. 3) JavaScript introduces concepts such as closures, prototype chains and Promise, which enhances flexibility and asynchronous programming capabilities.

Different JavaScript engines have different effects when parsing and executing JavaScript code, because the implementation principles and optimization strategies of each engine differ. 1. Lexical analysis: convert source code into lexical unit. 2. Grammar analysis: Generate an abstract syntax tree. 3. Optimization and compilation: Generate machine code through the JIT compiler. 4. Execute: Run the machine code. V8 engine optimizes through instant compilation and hidden class, SpiderMonkey uses a type inference system, resulting in different performance performance on the same code.

JavaScript's applications in the real world include server-side programming, mobile application development and Internet of Things control: 1. Server-side programming is realized through Node.js, suitable for high concurrent request processing. 2. Mobile application development is carried out through ReactNative and supports cross-platform deployment. 3. Used for IoT device control through Johnny-Five library, suitable for hardware interaction.

I built a functional multi-tenant SaaS application (an EdTech app) with your everyday tech tool and you can do the same. First, what’s a multi-tenant SaaS application? Multi-tenant SaaS applications let you serve multiple customers from a sing

This article demonstrates frontend integration with a backend secured by Permit, building a functional EdTech SaaS application using Next.js. The frontend fetches user permissions to control UI visibility and ensures API requests adhere to role-base

JavaScript is the core language of modern web development and is widely used for its diversity and flexibility. 1) Front-end development: build dynamic web pages and single-page applications through DOM operations and modern frameworks (such as React, Vue.js, Angular). 2) Server-side development: Node.js uses a non-blocking I/O model to handle high concurrency and real-time applications. 3) Mobile and desktop application development: cross-platform development is realized through ReactNative and Electron to improve development efficiency.

The latest trends in JavaScript include the rise of TypeScript, the popularity of modern frameworks and libraries, and the application of WebAssembly. Future prospects cover more powerful type systems, the development of server-side JavaScript, the expansion of artificial intelligence and machine learning, and the potential of IoT and edge computing.


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

Dreamweaver Mac version
Visual web development tools

SublimeText3 English version
Recommended: Win version, supports code prompts!

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

Atom editor mac version download
The most popular open source editor

SAP NetWeaver Server Adapter for Eclipse
Integrate Eclipse with SAP NetWeaver application server.