In our last article, we processed the heap, shift up, shift down, and so on.

This article introduces how to generate a maximum heap given an array.

Here is a random array, with the leaves in blue.

Think about:

  • Add the last (value: 62; Index: 10) compared to its parent (index/2).
  • Shift down.
  • This satisfies the maximum heap form, starting at the index value 5 and after its children.
  • Our array now looks like this:

Think about:

  • If index 10, and its parent index 5, satisfy the maximum heap condition.
  • Can the parent of its index 9 and 8 shift down to the maximum heap?
  • The answer is yes.
  • What about the parents of our indexes 6 and 7? What about the parents of indexes 4 and 5? What about the parents of indexes 2 and 3?
  • We find that by shift-down we end up converting a random array into the maximum heap.
  • Note, however, that when we calculate the parent of index 4 and 5, after index 2 and child indexes 4 and 5 are the maximum heap, the child indexes 8 and 9 of 4 will continue to be computed, or the child indexes 10 of 5 will continue to be computed, so that 4 and 5 will not shift down.

Take a look at the image below and compare it to the image above for reflection:

// For a given array, Heapify let arr = ["", 15, 17, 19, 13, 22, 16, 28, 30, 41, 62] let arrLength = arr.length function swap(arr, leftIndex, rightIndex) { [arr[leftIndex], arr[rightIndex]] = [arr[rightIndex], arr[leftIndex]] } function shiftDown(arr, k) { while (k * 2 <= arr.length) { let j = k * 2 if (j + 1 <= arr.length && arr[j + 1] > arr[j]) { j+=1; } if (! arr[j] || arr[k] > arr[j]) { break; } swap(arr, k, j) k = j; } return arr; } function heapify(arr, arrLength) { for (let i = parseInt((arrLength - 1) / 2); i >= 1; i--) { shiftDown(arr, i) } return arr; } console.log(heapify(arr, arrLength))Copy the code

Maximum heap sort

Although the last article introduced how to sort, but in order to avoid people to rummage, I will implement it again.

The following is the implementation, the general idea is in the remarks, the detailed idea is not written here, want to see or go to the last article to find it. Thank you for your support!!

Since we do not splice the array to generate the maximum heap, but we do splice the array to sort, a shiftDownd function can do both and return different values, so we need to wrap.

// For a given array, // Heapify let arr = ["", 15, 17, 19, 13, 22, 16, 28, 30, 41, 62] let arrLength = arr. Function swap(arr, leftIndex, rightIndex) {[arr[leftIndex], arr[rightIndex]] = [arr[rightIndex], Arr [leftIndex]]} Function check(arr){let arraySplice = arr.splice(arr.length-1, 1) let arrSpliceMax = arr.splice(1, 1) 1) arr.splice(1, 0, arraySplice[0]) return arrSpliceMax; } function shiftDown(arr, k, flag) { let arraySplice = []; if(flag){ arraySplice.push(... check(arr)) } while (k * 2 <= arr.length) { let j = k * 2 if (j + 1 <= arr.length && arr[j + 1] > arr[j]) { j += 1; } if (! arr[j] || arr[k] > arr[j]) { break; } swap(arr, k, j) k = j; } let arrMax = ! flag? arr : ArraySplice return arrMax} shift down function heapify(arr, arrLength) { for (let i = parseInt((arrLength - 1) / 2); i >= 1; i--) { shiftDown(arr, i, false) } return arr; } let arrayHeap = heapify(arr, arrLength); Console. log(arrayHeap) Shift downfunction heapSort(arr) {let array = [] for (let I =1; i < arr.length; i++) { array.push(... shiftDown(arr, 1, true)) } arr.splice(arr[0], 1) array = [...array, ...arr] return array } console.log(heapSort(arrayHeap))Copy the code