The algorithm that the front end of shallow solution must master (5) : Heap sort (2)

preface

Although rarely tested on front end of the interview algorithm class topics, but you go such as companies like tencent interview, grasp of the basic algorithm for our job in the computer science and technology, is indispensable, spend 10 minutes a day, easy to understand the basic concept of algorithm and the realization of the front end.

In addition, master some basic algorithm implementation, for our daily development, is also like a tiger added wings, can let our JS business logic more efficient and smooth.

Special instructions

I give each article positioning is 10 minutes should be mastered, because the knowledge structure needs to build more comprehensive, I take the initiative to split the heap sorting algorithm into the first and the next two articles, I hope to make you read more refreshing and happy.

You should hand itching to write algorithm, today we will look at how to use JS to achieve heap sort.

The article structure

Heap Sort (1)

Simple binary tree
Simple full binary tree
Simple complete binary tree
Simple pile of
Simple heap classification

Heap Sort (part 2)

Algorithm is introduced
Easy big top heap adjustment
Easy to create a big top heap
Easily implement heap sort
Complexity analysis

Algorithm is introduced

Heap sort is the method of sorting by heap (assuming using the big top heap).

The basic idea is to organize the numbers to be sorted into a big top heap. The maximum value of the entire array is the root node at the top of the heap. By removing it, you swap it with the last element of the heap array, which is the maximum. The remaining n-1 elements are then reconstructed from the heap, so that the sublarge value can be obtained again. Do this until there is only one element left, and you have an ordered array.

According to the above algorithm guidance, the following key operations can be figured out:

Max-heapify, which adjusts the end child of the heap so that the child is always smaller than the parent;
Create a build-max-heap where all the data in the Heap is repositioned so that it becomes a big Heap.
Heap-sort removes the root node at the top of the Heap and iterates on the large top Heap adjustment.

Easy big top heap adjustment

Max-heapify is the core subroutine to create the big top heap, which maintains the properties of the big top heap. The process of one action is shown in the figure below:

Schematic diagram of a large top stack adjustment

Since it is still possible to violate the properties of the big top heap after a single adjustment, the adjustment needs to be done recursively until the condition is satisfied for the entire heap.

/** * check from index and keep big top heap properties * @arr array to be sorted * @index check starting subscript * @heapsize heapSize **/
var maxHeapify = function(arr, index, heapSize) {
  // Compute the position relationship between a node and its left and right children
  // We saw that in the last section
  var iMax = index,
      iLeft = 2 * index + 1,
      iRight = 2 * (index + 1);

  // Whether the left child node has a larger value than the current node
  if (iLeft < heapSize && arr[index] < arr[iLeft]) {
    iMax = iLeft;
  }
  // Whether the right child node has a larger value than the current larger node
  if (iRight < heapSize && arr[iMax] < arr[iRight]) {
    iMax = iRight;
  }

  // If the value of the current node is not the largest of the three
  if(iMax ! = index) { swap(arr, iMax, index); maxHeapify(arr, iMax, heapSize);// Recursive adjustment}};var swap = function(arr, i, j) {
  var temp = arr[i];
  arr[i] = arr[j];
  arr[j] = temp;
};
Copy the code

The problem with the above code is that the recursive functions in the array can burst the stack if the array size is large. Then we might as well use iteration to achieve:

var maxHeapify = function(arr, index, heapSize) {
  var iMax, iLeft, iRight;
  do {
    iMax = index;
    iLeft = 2 * index + 1;
    iRight = 2 * (index + 1);

    // Whether the left child node has a larger value than the current node
    if (iLeft < heapSize && arr[index] < arr[iLeft]) {
      iMax = iLeft;
    }
    // Whether the right child node has a larger value than the current larger node
    if (iRight < heapSize && arr[iMax] < arr[iRight]) {
      iMax = iRight;
    }

    // If the value of the current node is not the largest of the three
    if (iMax != index) {
      swap(arr, iMax, index);
      index = iMax;
    }
  } while(iMax ! = index) }var swap = function(arr, i, j) {
  var temp = arr[i];
  arr[i] = arr[j];
  arr[j] = temp;
}
Copy the code

Easy to create a big top heap

Build-max-heap transforms an array into a large top Heap, taking both the array and the Heap size, where max-Heapify is called bottom-up to transform the array.

Because max-heapify guarantees that all nodes after the subscript I are big top heap properties, we invoke max-Heapify bottom-up.

If the total number of elements in the maximum Heap is N, the build-max-heap is created starting with getParentPos(n) and then max-heapify is called upward. The process is shown in the figure below:

Schematic diagram of creating a big top heap

The algorithm is as follows:

var buildMaxHeap = function(arr, heapSize) {
  var i, iParent = Math.floor((heapSize - 1) / 2);

  for (i=iParent; i>=0; i--) { maxHeapify(arr, i, heapSize); }}Copy the code

Easily implement heap sort

Heap-sort is an interface algorithm for Heap sorting, which first calls build-max-heap to transform an array into a big Heap. An iteration is then carried out, in which the top and bottom elements are swapped and the heap length is shortened, and max-heapify is re-invoked to preserve the big-top nature.

Since the top element is necessarily the largest element in the heap, after each operation, the largest element in the heap is separated from the heap, repeated n-1 times, and the array is sorted. The process is shown in the figure below:

Schematic diagram of heap sort process

The algorithm is as follows:

var heapSort = function(arr, heapSize){
  var i;

  buildMaxHeap(arr, heapSize);
  for (i=heapSize- 1; i>0; i--) {
    swap(arr, 0, i);
    maxHeapify(arr, 0, i); }};Copy the code

Complete implementation

Based on the above three pieces of code, the complete JS code is as follows:

/* Big top heap sort */
var heapSort = function(arr, heapSize){
  var i;

  buildMaxHeap(arr, heapSize);
  for (i=heapSize- 1; i>0; i--) {
    swap(arr, 0, i);
    maxHeapify(arr, 0, i); }};/* Create a big top heap */
var buildMaxHeap = function(arr, heapSize) {
  var i, iParent = Math.floor((heapSize - 1) / 2);

  for (i=iParent; i>=0; i--) { maxHeapify(arr, i, heapSize); }};/* Big top heap adjustment */
var maxHeapify = function(arr, index, heapSize) {
  var iMax, iLeft, iRight;
  do {
    iMax = index;
    iLeft = 2 * index + 1;
    iRight = 2 * (index + 1);

    // Whether the left child node has a larger value than the current node
    if (iLeft < heapSize && arr[index] < arr[iLeft]) {
      iMax = iLeft;
    }
    // Whether the right child node has a larger value than the current larger node
    if (iRight < heapSize && arr[iMax] < arr[iRight]) {
      iMax = iRight;
    }

    // If the value of the current node is not the largest of the three
    if (iMax != index) {
      swap(arr, iMax, index);
      index = iMax;
    }
  } while(iMax ! = index) }var swap = function(arr, i, j) {
  var temp = arr[i];
  arr[i] = arr[j];
  arr[j] = temp;
}
Copy the code

Complexity analysis

The running time of heap sort is mainly consumed by repeated filtering when the heap is initially built and rebuilt.

We won’t go into the time complexity of the algorithm here, but in general, the time complexity of heap sort is O(n*logn). Since heapsort is insensitive to the sort state of the original array, it is O(n*logn) for best, worst, and mean-time complexity. This is obviously better in performance than bubbling, simple selection, direct insertion and other O(n^2) algorithms.

Also, because of the number of comparisons required to initialize the build heap, it is not suitable for arrays with fewer elements.

Refer to the link

Bubkoo.com/2014/01/14/…

Zh.wikipedia.org/wiki/%E5%A0…

If you think this article is good, share it with your friends