Although in the front-end interview, algorithm inspection will not be particularly difficult, but the basic sorting algorithm, we need to be familiar with the principle of sorting algorithm, can not speak out, may be a minus points. Because it is fundamental to our ability as programmers, algorithms improve our ability to solve problems. So whether you interview or not, mastering it will definitely benefit your career (💰). After all, sorting algorithms are the foundation of all algorithms.😄

In fact, after I read the sorting algorithm chapter in Algorithm 4, HEapsort is probably one of the more difficult classical sorting algorithms to understand, but it’s very clever and interesting. This piqued my interest in algorithms, and hopefully yours, 😝

  • What does the text say?
  1. Definition and implementation of heap-ordered binary tree structure
  2. What does a priority queue look like?
  3. How do we derive classical heapsort from priority queues?

  • Other sorting algorithm source stamp here

  • I will continue to update the diagrams for other algorithms and plan to update the source code series for Vue2.6 starting next month. Of course, everything will revolve around the interview. Please follow us like ❤️

Heap sort

To understand heap sorting, we first need to understand his heap-ordered binary tree of data structures

Heap-ordered binary tree

  • The term has to be understood separately, “heap order” and “binary tree “.

Binary tree

A binary tree is simply “a tree that requires each branch to branch only once.”

  • This graph is nice and is a standard binary tree ✅

  • This is not true, it is a multi-fork tree ❌

Orderly heap

  • First of all, let’s look at the definition in the fourth edition of the algorithm,

Definition A binary tree is called heap-ordered when each node is greater than or equal to two of its children.

So let’s say we have these numbers: 10, 5, 6, 1, 4, 3, and we think of it as an array, but for the sake of calculation, we don’t consider the 0 bits, so it looks like this

const arr = [ <1 empty item>, 10, 5, 6, 1, 4, 3 ]
Copy the code

We make two agreements:

  1. We assume the current indexifork, it is2kFor the currentkChild node of.

For example, if the current index K is 1, its child node’s index is 2.

  1. We assume the current indexifork, it isk / 2For the currentkParent node of.

For example, if the current index K is 4, its parent node is 2. However, there are some odd nodes, so we add a constraint to facilitate calculation. We wrap math.floor () every time we find the parent node.

If a node has an index of 3, we count its parent node this way. This prevents the index from becoming a decimal (1.5)

Math.floor( k / 2 )
Copy the code

Ok, at this point we can draw a graph like 👇👇👇 by using the two conventions mentioned above

If you look closely at the graph, there seems to be a pattern. Each child node seems to be smaller than its parent, and it looks like a binary tree.

Yeah, that’s satisfied. So our definition above, just to recap here is that when every node in a binary tree is greater than or equal to two of its children, it’s called heap order.

Figure:

Such an array, we can think of it as a heap-ordered binary tree (from here, we will call it a binary heap for short), yes, an array can be used to represent a binary heap.

If you look closely at the figure above, you can see that if an array satisfies a binary heap. Then its root node will always be the largest in the array. And that’s what we’re going to talk about heap sorting.

At this point, we have a train of thought. Just extract the root of the array each time and reorder it so that the root must be the largest value each time. Open made 😝

How do I order an array heap?

First, we need a method to insert data into an array.

const pq = [] // Suppose this is a binary heap

function insert (value) {
    pq[pq.length] = v
}
Copy the code

When we insert an element, it may scramble the binary heap, for example, if we insert a 10 in bit 4, the parent of bit 2, or bit 4, may be 2. That doesn’t satisfy the binary heap condition.

In the second step, we need to reorder the heap each time we insert elements, which is equivalent to bottom-up heap ordering

    const pq = [] // Suppose this is a binary heap

    function insert (value) {
        pq[pq.length] = v
+       swim(pq.length) // Define an up-float method that passes in the index of the current value
    }
    // Bottom-up heap ordering
+   function swim (k) {+let pJ = Math.floor( k / 2 ) // Get the index of the parent node
+       while(k > 1 && pq[k] >= pq[pJ]) {
+           exch(k, pJ)
+           k = pJ // Keep looking up+ +}}Copy the code
  • Ok, so we’re done adding elements and ordering the heap

You don’t have to understand how the graph compares, you just have to feel the flow, right

Third, extract the root node.

  • Deleting an element is easy, and we won’t go into details here. We simply swap the top element with the last one in the function, and then empty the index
function delMax () {
    const max = pq[1]
    exch(1, pq.length - 1)
    pq[pq.length - 1] = null / / to empty
    return max
}
Copy the code

The problem with this is that the bottom nodes are moved to the root, so you need to order the array from the top down

    function delMax () {
        const max = pq[1]
        exch(1, pq.length - 1)
        pq[pq.length - 1] = null / / to empty
+       this.sink(1) // The heap is ordered
        return max
    }
    // Order the heap from top to bottom
+   function sink (k) {+while(k < pq.length) {
+           let j = 2 * K / / child nodes
+           if (j < pq.length && pq[j] < pq[j + 1]) j++;
+           if(pq[k] > pq[j]) break;
+           exch(k, j) // Otherwise swap
+           k = j // Keep looking down+ +}}Copy the code

Now, this is actually all of the functionality of a priority queue class. The above code has broken it up into functional functions to make it more user-friendly. The complete class can be seen in the priority queue MaxPQ

Flowchart of two operations

Now that we know that there are two ways to turn an array into a binary heap, namely sink() and swim(), we need to consider which one is more suitable for our heap sorting algorithm.

  1. Loops through elements from left to right and callsswim(), so that the entire array is ordered,
  2. Call from right to leftsink()Method to sink each element.

Obviously the second course is smarter. Why?

Because the second approach, we only need in the first half of scanning array, we can assume that each array element is a pile of orderly child nodes, and for the second half of the array, they are at the very bottom of the tree. (such as an array of length of 10, obviously can’t be 12 6 node as a child node)

The principle of heap sort

Now that we understand how heap sort works, we need to understand how heap sort works.

  1. Converts the given array to a binary heap
  2. Defines a pointer to the last digit of the array
  3. Swap the root node of the binary heap (maximum) with the current pointer bit, then move the pointer one bit to the left
  4. Call array index 0 to pointer oncesink(), reorder the heap

Step 3 is the heart of heap sort, essentially putting the maximum value in the last bit of the array and not participating the next time the heap is sorted. Because we are sorting and ordering the heap on an array, we need a pointer to distinguish sorted elements from elements to be sorted

  1. Converts the given array to a binary heap
  2. Defines a pointer to the last digit of the array
function sortArray (nums: number[]) {
    let N  = nums.length - 1
    // Starting from the middle, pointer I moves to the left
    for(let i = Math.floor(N / 2); i >= 0; i--) {
        // Heap the I through N elements until the top of the number group
        sink(nums, i, N)
    } 
}
Copy the code
  1. Swap the root node of the binary heap (maximum) with the current pointer bit, then move the pointer one bit to the left
  2. Call array index 0 to pointer oncesink(), reorder the heap

Copy jump heap sort is required

+ function sink (nums: number[], k: number, N: number) {+while (k * 2 <= N) {
+         let j = k * 2 / / child nodes
+         if (j < N && nums[j] < nums[j + 1]) j++
+         if (nums[k] >= nums[j]) break;
+         exch(nums, k, j)
+         k = j
+     }
+  }
  function sortArray (nums: number[]) {
      let N  = nums.length - 1
      // Starting from the middle, pointer I moves to the left
      for(let i = Math.floor(N / 2); i >= 0; i--) {
          // Heap the I through N elements until the top of the number group
          sink(nums, i, N)
      } 
+     while (N > 0) {
+         exch(nums, 0, N--) // Swap the first and last digits, and move the pointer left
+         sink(nums, 0, N) // The pointer moves backward to order the heap+},return nums
  }
Copy the code

Note: We left the first digit of the instance array empty when we talked about the various APIS of priority queues for easy computation and more binary tree generation, but I didn’t do that in the heap-ordered algorithm. This can result in only one node below the root (making the tree one more level), but I’ve ignored this for brevity.

Such as:

let arr = [3.2.1.5]
/ / heap in order
let suckArr = [ 5.3.1.2 ]
Copy the code

The images in this article are from the fourth edition of Algorithms

Thank 😘

If you find the content helpful:

  • ❤️ welcome to focus on praise oh! I will do my best to produce high-quality articles

Contact author: Linkcyd 😁 Previous:

  • React Get started with 6 brain maps
  • Interviewer: Come on, hand write a promise
  • That’s all you need to know about regular expressions