Heap Sort

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.

What is a heap?

A heap is actually a special kind of tree. As long as these two things are true, it’s a heap.

  • The heap is a complete binary tree (the number of nodes is full except for the last layer, which is arranged to the left).
  • The value of each node in the heap must be greater than or equal to (or less than or equal to) the value of each node in its child tree.

A heap with each node greater than or equal to the value of each node in the subtree is called a large top heap. (Forward sort)

A small top heap is a heap where the value of each node is less than or equal to the value of each node in the subtree. (Reverse order)

Figure 1 and figure 2 are the big top heap, Figure 3 is the small top heap, and Figure 4 is not a heap. In addition, as you can see from the figure, we can build many different types of heap for the same set of data.

Algorithm description

  1. Build the sequence to be sorted into a big top heap, which is the initial unordered region (actually, at this time, ARR [0] is already the maximum, as shown in Figure 1 and Figure 2, so it is necessary to continue sorting child nodes)
  2. The top of the heap is swapped with the last element to obtain ordered and unordered sequences, with all elements of the unordered sequence less than the smallest element of the ordered sequence
  3. After the exchange, the heap was destroyed, and the big top heap was rebuilt. Step 2 arr. Length-1 was repeated, and the sorting was completed.

Dynamic graph demonstration

I don’t understand one graph at all.

Code implementation

            let arr = [3.45.16.8.65.15.36.22.19.1.96.12.56.12.45];
            let len = arr.length;
            let heapSort = arr= > {
                // Build the big top heap
                for (let i = Math.trunc(len / 2 - 1); i >= 0; i--) {
                    heapify(arr, i, len);
                }
                // After the build is complete, continue to build the big top heap for the remaining elements
                for (let i = Math.floor(arr.length - 1); i > 0; i--) {
                    // Swap the root element (minimum or maximum) with the last element
                    swap(arr, 0, i);
                    // Continue building the big top heap
                    heapify(arr, 0, i);
                }
                console.log(arr);
            };
            let swap = (arr, i, j) = > {
                let temp;
                temp = arr[i];
                arr[i] = arr[j];
                arr[j] = temp;
            };
            // Make the heap below I into a big top heap. Note that this step is based on:
            // Assume that the subheap below node I is already a big top heap, as implemented by heapify
            // Find node I in the heap containing node I.
            // We will write a for loop, starting at the first non-leaf node, for each non-leaf node
            // All heapify operations are performed, so the subheap below node I is already a big top heap
            let heapify = (arr, i, length) = > {
                let temp = arr[i];
                for (let j = 2 * i + 1; j < length; j = 2 * j + 1) {
                    if (j + 1 < length && arr[j] > arr[j + 1]) {
                        j++;
                    }
                    if (temp > arr[j]) {
                        swap(arr, i, j);
                        i = j;
                    } else {
                        break; }}}; heapSort(arr);Copy the code

Results:

Heap sort consists of two operations: heap build and sort. The time complexity of heap build is O(n), and the time complexity of sort is O(nlogn). Therefore, the overall time complexity of heap sort is O(nlogn). Best case: T(n) = O(nlogn). Worst case: T(n) = O(nlogn). Average case: T(n) = O(nlogn).

In addition, heap sort is an unstable sort from the administrative point of view of heap.

conclusion

Heap sort is also a kind of selection sort. It may sound like a very fancy sort by name, but it’s actually a lot simpler than other sorts (at least, it’s a lot simpler than Hill sort HHH). The key is to understand what a heap is, and what is a big top heap versus a small top heap

reference

  • Five minutes to understand a difficult sort: heap sort
  • Top ten classic front-end algorithms
  • The beauty of JavaScript data structures and algorithms – merge sort, quicksort, Hill sort, heap sort

Next up

Front-end sorting Algorithm No.4 (Quicksort for another swap sort)