Let’s start with normal queues and priority queues:

Common queue: first in first out, last in last out.

Priority queue: the queue exit order has nothing to do with the queue entry order; It has to do with priorities.

Priority queue

Why use priority queues? Here’s an example:

Select the first M elements out of N elements.

  • Sorting time complexity: NlogN
  • Priority queue time complexity: NlogM

The speed of the priority queue is faster than that of the normal queue.

The heap

The data structure of the heap is a binary tree. Like these two images: A binary tree in which the value of a node in the heap is never greater than the value of the parent node is called a complete binary tree.

So, the heap is always a complete binary tree.

The biggest one at the top is called the biggest heap. The minimum at the top is called the minimum heap.

Features:

  • The value of a node is always no greater than the value of the parent node.
  • The last row may not be full, but it will definitely be on the left.

The heap data structure is still stored in arrays, and the nodes are regular, as shown in the following figure:

  • The nodes on the left start at the top and go down and multiply by two.
  • The node on the right starts at the top and goes down by 2 plus 1.

This is setting vertex 62 at 1, which would be zero if it were perfectly structured.

Then the rules change. Be careful.

Maximum heap of added elements

Assuming that we now have a maximum heap, is above the array [“, “62,41,30,28,16,22,13,19,17,15]

Now we’re going to add an element 52 to this maximum heap, insert it in the right place.

Think about:
  • Since it’s an array, you must have put 52 at the end of the array first.
  • The subscript of 52 is 11.
  • And then the heap doesn’t fit the definition of the largest heap, because 52 is bigger than 16.
  • If you’re bigger than 16, you have to switch places with 16. So I want to find the index of 16.
  • And the way to find the index is by saying that the index of 52 is an odd number 11, 11 minus 1 over 2 is the index of 16.
  • Just switch places when you find it.

Look at the following code:

let arr = ["", 62, 41, 30, 28, 16, 22, 13, 19, 17, 15] function main(arr, Num) {arr.push(num) let maxIndex = arr. length-1 let k = math.floor (maxIndex / 2) // While (k > 1 &&arr [k] < Arr [maxIndex]) {// Switch position [arr[k], arr[maxIndex]] = [arr[maxIndex], arr[k]] maxIndex = k k = Math.floor(maxIndex / 2) } return arr } console.log(main(arr, 52))Copy the code

Shift Down (Shift Down)

Now our array is: [“, 62, 52, 30, 28, 41, 22, 13, 19, 17, 15, 16]

It still satisfies the maximum heap condition, so if you take an element out of the heap, it still satisfies the maximum heap condition.

Condition:
  • When you take an element out of the heap, you can only take the element at the root node, which is 62.
Think about:
  • When we get out of the maximum heap, the root element.
  • We’re missing an element in our maximum heap. How do we fill that element?
  • The last element is placed directly in the first place, and the two nodes below it are compared.
  • Swap places with whoever is older. So you’re guaranteed to have more numbers than 16 or 30. Satisfies the maximum heap property.
  • And then you keep comparing.
// shift down let arr = ['', 62, 52, 30, 28, 41, 22, 13, 19, 17, 15, 16]; function shiftDown(arr, k) { arr.splice(1, 1) let array = arr.splice(arr.length - 1, 1) arr.splice(1, 0, array[0]) let count = arr.length // ['', 16, 52, 30, 28, 41, 22, 13, 19, 17, While (k * 2 <= count) {let j = k * 2 // if (j + 1 <= count &&arr [j + 1] > arr[j]) { j += 1 } if (arr[k] >= arr[j]) { break } [arr[k], arr[j]] = [arr[j], arr[k]] k = j } return arr } console.log(shiftDown(arr, 1));Copy the code

Heap sort

We know what the maximum heap is, we know how to add an element to order it, and we know how to order it when we take an element out. So how do you get the largest heap to sort from smallest to largest, or from largest to smallest?

Think about:
  • Shift Down, if you take out the maximum value each time, return.
  • For the rest of the sorting, repeat return out.
  • So that’s the solution.
  • If a new value is added to the array, shift up.
  • Shift down again.
// heapSort1 let arr = [", 62, 52, 30, 28, 41, 22, 13, 19, 17, 15, 16]; Function swap(arr, leftIndex, rightIndex) {[arr[leftIndex], arr[rightIndex]] = [arr[rightIndex], Arr [leftIndex]]} // Take the maximum value from shiftIndex // return the rest of the order, Function shiftDown(arr, k) {let array = arr.splice(arr.length-1, 1); let spliceArray = arr.splice(1, 1) arr.splice(1, 0, array[0]); while (k * 2 <= arr.length) { let j = k * 2; if (j + 1 <= arr.length && arr[j + 1] > arr[j]) { j += 1; }; // undefined is added! Arr [J] judge if (! arr[j] || arr[k] >= arr[j]) { break; } swap(arr, k, j) k = j; }; return spliceArray; } function heapSort1(arr) { let array = [] for (let i = 1; i < arr.length; I++) {// take the maximum value and sort the rest until the end of array.push(... shiftDown(arr, 1)) } arr.splice(0, 1) array = [...array, ...arr] return array; } console.log(heapSort1(arr)) // [62, 52, 41, 30, 28, 22, 19, 16, 17, 15, 13]Copy the code

Conclusion:

This is just a maximum heap sort, but if it’s not the maximum heap, you might want to do quicksort or insert sort or something like that.

But the next thing to think about is, for any array, how do I make a maximum heap?

The reason to think about this is: the largest data indicates that this data has the highest priority. After taking out this data, how to determine the next priority? Do you still need to shift down?

Do you feel that the algorithm is not useless, but you don’t use it, or don’t know how to use it?

Let’s keep learning together…