Home > Web Front-end > JS Tutorial > body text

Detailed explanation of heap sort in JavaScript

韦小宝
Release: 2018-03-14 14:22:19
Original
2091 people have browsed it

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

Detailed explanation of heap sort in JavaScript

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;}
Copy after login

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!

Related labels:
source:php.cn
Statement of this Website
The content of this article is voluntarily contributed by netizens, and the copyright belongs to the original author. This site does not assume corresponding legal responsibility. If you find any content suspected of plagiarism or infringement, please contact admin@php.cn
Popular Tutorials
More>
Latest Downloads
More>
Web Effects
Website Source Code
Website Materials
Front End Template