This is the 16th day of my participation in the November Gwen Challenge. Check out the event details: The last Gwen Challenge 2021

We learned about sorting methods in the last article, and we learned more about JavaScript in this series

In this article, we will continue to learn the classic sorting method: Heapsort

JS implementation of the sort algorithm – Heapsort Heapsort

Heapsort refers to a sort algorithm designed by using heap data structure. Heap is a nearly complete binary tree structure, and also satisfies the property of heap: that is, the key value or index of the child node is always smaller (or larger) than its parent node. Heap sort can be said to be a selection sort that uses the concept of heap to sort. The average time complexity of heap sort is two o (nlogn).

Heap sort is divided into two methods:

  1. Big pile top: The value of each node is greater than or equal to the value of its children, used in the heap sort algorithm for ascending order;
  2. Small cap pile: The value of each node is less than or equal to the value of its children, which is used for descending order in the heap sort algorithm;

Heapsort algorithm steps

  1. Build the sequence to be sorted into a heapN - 1) H [0..., according to (ascending descending requirements) to select the big top heap or small top heap;
  2. Swap the heap head (maximum) with the heap tail;
  3. Reduce the size of the heap by 1 and callshift_down(0), the purpose is to adjust the top of the new array to the corresponding position;
  4. Repeat step 2 until the heap size is 1.

Heap sort JS code implementation:

  1. Function encapsulation
var len // Since multiple declared functions require data length, len is set as a global variable

function buildMaxHeap(arr) {
  // Create a big top heap
  len = arr.length
  for (var i = Math.floor(len / 2); i >= 0; i--) {
    heapify(arr, i)
  }
}

function heapify(arr, i) {
  / / heap of adjustment
  var left = 2 * i + 1,
    right = 2 * i + 2,
    largest = i

  if (left < len && arr[left] > arr[largest]) {
    largest = left
  }

  if (right < len && arr[right] > arr[largest]) {
    largest = right
  }

  if(largest ! = i) { swap(arr, i, largest) heapify(arr, largest) } }function swap(arr, i, j) {
  var temp = arr[i]
  arr[i] = arr[j]
  arr[j] = temp
}
Copy the code
  1. Sorting algorithmheapSort()function
function heapSort(arr) {
  buildMaxHeap(arr)

  for (var i = arr.length - 1; i > 0; i--) {
    swap(arr, 0, i)
    len--
    heapify(arr, 0)}return arr
}
// Introduce the following method to test the code time:
getFnRunTime(heapSort)
Copy the code

Code runtime method

const testArrFn = function () {
  let arr = []
  const count = 200000
  for (let i = 0; i < count; i++) {
    arr[i] = Math.floor(Math.random() * 50 + 1)}return arr
}
let testArr = testArrFn()

let len = testArr.length
/ * * *@desc Test function execution time */
module.exports = async function getFnRunTime(fn) {
  let startTime = Date.now(),
    endTime
  let result = await fn(testArr)
  endTime = Date.now()
  console.log(testArr, result)
  console.log(`total time: ${endTime - startTime}ms, `."test array'length: " + len, result.length)
}
Copy the code

Read more

  • 】 【 Array. The prototype. The map (),
  • JS- special symbol – bit operator
  • 【ES6 – for/of】,
  • JS- Logical operator – short circuit? ,
  • 【JS- arrow function 】
  • 】 【 JavaScript – forEach (),

Classical sorting algorithm:

  • 【 jS-sort algorithm -sort()】,
  • 【JavaScript- sort algorithm – Hill sort 】
  • 【JS- sorting algorithm – merge sort 】,
  • 【JavaScript- sorting algorithm – counting sort 】
  • 【JS- sort algorithm – bubble sort 】