This is the third day of my participation in the November Gwen Challenge. Check out the details: the last Gwen Challenge 2021

The heap

A heap is a nearly complete binary tree structure that satisfies both heap-like properties: the key or index of a child node is always greater than (the big top heap) or less than (the small top heap) its left and right child nodes. It has a worst-case, best-case, and mean time complexity of O(nlogn), and it is also an unstable sort.

Basic idea of algorithm

  1. The sequence to be sorted forms a big top heap, and the maximum value of the entire sequence is the root node of the top of the heap
  2. Swap it with the last element, which is the maximum
  3. The remaining n-1 elements are then reconstituted into a heap to get the second smallest value of n elements, and this is repeated to get an ordered sequence

Data structure parsing

A heap is a set of data maintained in a complete binary tree structure

Complete binary tree: Let the depth of the binary tree be H, except for the h layer, the number of nodes in all other layers (1-H-1) reaches the maximum, and all nodes in the h layer are continuously concentrated in the leftmost tree.

Small root heap: A heap in which the left and right children of each node in the heap are less than that node is called the minimum heap (often referred to as less than or equal to).

heap[i]< heap[2i+1] && heap[i]< head[2i+2]

Large root heap: A heap in which the left and right children of each node in the heap are greater than that node is called the minimum heap (often referred to as greater than or equal to)

heap[i]>heap[2i+1] && heap[i]> head[2i+2]

Complexity resolution

Heap sort is a kind of selective sort in nature, which mainly consists of constructing the initial heap and exchanging the top elements of the heap and rebuilding the heap. Wherein, the initial heap construction is pushed to the complexity of O(n) by exchanging the top elements of the heap and rebuilding the heap. The cycle is n-1 times, and each time it is searched from the root node downwards. Therefore, the time of each cycle is logn, and the total time is logn(n-1) = nlogn-logn; So the time is O(nlogn) because heapsort is sort in place, there’s no recursion, there’s no extra space, so the space is O(1).

Stability analysis

Suppose there are multiple records with the same keyword in the sequence of records to be sorted, and the relative order of the records remains the same after sorting

That is, if Ri = Rj and Ri precedes Rj in the original sequence, and Ri precedes Rj in the sorted sequence, the sorting algorithm is said to be stable; otherwise, it is said to be unstable

Consider the sequence {9, 5a, 7, 5b} and follow the heapsort algorithm to walk through it. It will soon be found that the output sequence {5b, 5a, 7, 9} is independent of the equal sign, so it is obvious that the heapsort is unstable.

Usage Scenario Analysis

Compared with quicksort and merge sort, heapsort is more suitable for situations with large data volume. For example, heapsort does not require a large amount of recursion or multi-dimensional temporary array to deal with some scenarios with more than millions of records, which is very suitable for sequences with large data volume. However, both quicksort and merge sort use recursive design algorithms, and stack overflow errors may occur when the amount of data is very large

Code implementation

JAVA implementation

/** * Select sort - heap sort *@param Array Array to be sorted *@return Sorted array */
public static int[] heapSort(int[] array) {
    // The element index starts at 0, so the last non-leaf node is array.length/ 2-1
    for (int i = array.length / 2 - 1; i >= 0; i--) {  
        adjustHeap(array, i, array.length);  / / adjust the heap
    }

    // Build the heap
    // Start the sorting logic
    for (int j = array.length - 1; j > 0; j--) {
        // Swap elements to remove the big top heap
        // Place the root element of the big heap at the end of the array; In other words, after each heap adjustment, one element reaches its final position
        swap(array, 0, j);
        // After the element swap, there is no doubt that the last element does not need to be sorted.
        // The next thing we need to sort is the heap that has removed some elements. That's why this method is in the loop
        // In this case, the adjustment is essentially top-down, from left to right
        adjustHeap(array, 0, j);
    }
    return array;
}

/** * the most important part of the heap sort *@param Array Heap to be group *@param I start node *@param Length Indicates the length of the heap */
public static void adjustHeap(int[] array, int i, int length) {
    // Take the current element out first, because the current element may keep moving
    int temp = array[i];
    for (int k = 2 * i + 1; k < length; k = 2 * k + 1) {  //2* I +1 is the left subtree of I (since I starts at 0), and 2*k+1 is the left subtree of k
        // let k refer to the largest of the children first
        if (k + 1 < length && array[k] < array[k + 1]) {  // If there is a right subtree and the right subtree is larger than the left subtree
            k++;
        }
        // If the node (left and right children) is found to be larger than the root, the value is swapped
        if (array[k] > temp) {
            swap(array, i, k);
            // If the child node is changed, then the root of the child node will be affected, so the loop continues to judge the tree in which the child node is located
                i  =  k;
                    } else {  // Terminate the loop without switching
            break; }}}/** * swap elements *@param arr
* @param The subscript star of the element A@param The subscript of the b element */
public static void swap(int[] arr, int a, int b) {
    int temp = arr[a];
    arr[a] = arr[b];
    arr[b] = temp;
}

Copy the code

JavaScript implementation

var len;
function buildMaxHeap(arr) { // Create a big top heap
  len = arr.length;
  for (let 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 the code