Detailed explanation of heap sort in JavaScript

This article talks about heap sorting in JavaScript. If you don’t know about heap sorting in JavaScript or are interested in heap sorting in JavaScript, then let’s take a look at this article. Okay, enough nonsense. Let’s get to the point

Heap sort can be said to be a selection sort that uses the concept of heap to sort. Divided into two methods:

1, Big 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

2, 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 sort algorithm

Heap sort animation Demonstration

JavaScript code implementation:

var len;    //因为声明的多个函数都需要数据长度，所以把len设置成为全局变量function buildMaxHeap(arr) {   //建立大顶堆  
    len = arr.length;  
    for (var i = Math.floor(len/2); i >= 0; i--) {  
        heapify(arr, i);  
    }}function heapify(arr, i) {     //堆调整  
    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;}function heapSort(arr) {  
    buildMaxHeap(arr);  
  
    for (var i = arr.length-1; i > 0; i--) {  
        swap(arr, 0, i);  
        len--;  
        heapify(arr, 0);  
    }  
    return arr;}

The above is all the content of this article. If you don’t know much about it, you can implement both sides by yourself. It’s easy to master!

Related recommendations:

JavascriptHeap sortDetailed explanation of algorithm

The above is the detailed content of Detailed explanation of heap sort in JavaScript. For more information, please follow other related articles on the PHP Chinese website!