堆排序 （一，shift up、shift down、heapSort）

先来介绍一下普通队列和优先队列：

普通队列：先进先出，后进后出。

优先队列：出队顺序和入队顺序无关；和优先级有关。

优先队列

为什么要使用优先队列？举个例子：

在N个元素中选出前M个元素。

• 排序的时间复杂度：NlogN
• 优先队列的时间复杂度：NlogM

可见优先队列的速度是比普通队列快的。

堆

堆的数据结构是二叉树。就像下面这两张图： 堆中某个节点的值，总是不大于父节点的值，这样的二叉树结构，叫做完全二叉树。

所以，堆总是一棵完全二叉树。

最大值在顶的，叫做最大堆。最小值在顶的叫做最小堆。

特点：

• 某个节点的值，总是不大于父节点的值。
• 最后一行可能不会是满的，但是一定会在左侧。

堆这种数据结构，依然是用数组来存储的，节点是有规律的，看下面这张图：

• 左面的节点从顶开始，往下，都是乘以二。
• 右边的节点从顶开始，往下，都是乘2加1。

这是将顶点62的位置规定为1了，如果是完全符合数组的结构，62的位置应该是0。

这样规律就会发生改变。一定要注意。

最大堆添加元素

假设我们现在有一个最大堆，就是上图那个数组["",62,41,30,28,16,22,13,19,17,15]

我们现在要往这个最大堆中添加一个元素52，插入到正确的位置。

思考：

• 既然是数组，肯定是先将52放入到数组的末尾了。
• 那52的下标就是11。
• 放入之后这个堆就不符合最大堆的定义，因为52比16大。
• 既然比16大就要和16交换位置。所以要找到16的索引。
• 找索引的办法就是通过我们之前说的，52索引是奇数11，(11-1)/2就是16的索引。
• 找到之后交换位置就可以了。

看下面的代码：

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]) {                        
        // 交换位置                                
        [arr[k], arr[maxIndex]] = [arr[maxIndex], arr[k]]                     
        maxIndex = k                        
        k = Math.floor(maxIndex / 2)            
    }            
    return arr
}
console.log(main(arr, 52))

最大堆取出一个元素（Shift Down）

现在我们的数组是：[ '', 62, 52, 30, 28, 41, 22, 13, 19, 17, 15, 16 ]

依然满足最大堆条件，从堆中取出一个元素，让它依然满足最大堆。

条件：

• 从堆中取出一个元素，只能取根节点的元素，也就是62这个元素。

思考：

• 当我们从最大堆中出去根节点的元素。
• 我们的最大堆中就相当于少了一个元素，如何填补这个元素？
• 将最后一位的元素直接放在第一位，然后它下面的两个节点进行比较。
• 谁大就与谁交换位置。这样就保证了，换上来的数比16和30都大。满足最大堆性质。
• 然后继续不断比较。

// 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, 15]
	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));

堆排序

我们知道了什么是最大堆，也知道如何添加一个元素后排好序，还知道取出一个元素后如何排好序。 那，如何让一个最大堆，完成从小到大的排序，或者从大到小的排序呢？

思考：

• Shift Down这步，如果将每次取出来的最大值，return 出去。
• 剩下的排序，重复 return 出去这步操作。
• 就解决了这样的问题。
• 如果添加了一个新的值，在数组中，就shift up。
• 再shift down。

// 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]]
}
// 将最大堆 shiftDown
// return 每次取出的最大值 spliceArray
// 剩下的排序，之后继续取出最大值
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， 所以加入了!arr[j]判断
    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++) {
    // 遍历的方式，取出最大值，将剩下的排序，直到结束
    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]

总结：

这只是一个最大堆的排序方式，如果不是最大堆，你可能会选择快速排序或者插入排序等。

但是接下来要思考，任意数组，如何生成一个最大堆？

要思考这个的原因是：数据最大表示这个数据优先级最高，取出这个数据之后，接下来的优先级如何确定？是不是还是需要用到shift down？

是不是觉得，算法原来不是没有用处的，而是你没用到，或者不知道怎么用？

让我们一起继续学习吧。。。。