Day21:[排序演算法]Heap Sort - 堆积排序法

heap sort的原理是采用max heap这种资料结构来做排序，max heap是一种binary tree，每个节点都会比自己的子节点还大，因此根节点会是最大值，让我们先来理解如何实作一个max heap吧!假设现在有一个排序是乱的binary tree如下图

先从右边的subtree开始，如果subtree的父节点不是最大值就跟子节点做交换，7跟9交换

红色圈起来的就是subtee(子树)
15已是最大值，所以不用跟子节点交换
16为最大值，故与3做交换
12与8做交换
当最下层的节点都遍历完了，就轮到上面一层，15与11交换，不过这时候会发现一个问题，交换过後11, 10 ,14这个subTree并不是一个max heap，因此还要再做一次交换
因此14与11交换，每次交换的时候都要检查下一层的值是否有比当前的值还大，有的话当前值就要跟较大值对调位置

这样依序的交换过一轮最後就会获得一个max-heap!

理解了max-heap的运作原理之後，就可以来探讨如何用max-heap做heap sort了。

先将根节点(16)与leaf node最右边的节点(4)做交换，此时4会在根节点的位置，16会跑到右下角，接着移除右下角的节点并取出16放在下方，这时会发现4并不是这整颗树里面的最大值，因此4要向下交换

绿色的数字为取出的数字

交换过後如果发现下面还有比自己更大的值就要一直交换下去，最後4来到了这个位置

经过一轮交换，最後4停留在这个位置
这时会发现15已经是整个max-heap的最大值，於是跟leaf node下层最右边的节点7做交换，再把15从节点中抽离出来，接下来就是一直不断的重复这个动作

如果还是觉得有点抽象的话，可以参考heap sort的流程的gif，应该可以帮助理解，画面中的heapify指的是将根节点一路向下交换的过程

图片来源:Cakeresume.com

用js实作max heap

首先先将tree转换成阵列，由上到下将每个节点取出的话，可以得到一个阵列[5, 13, 11, 8, 3, 15, 7, 12, 2, 16, 6, 10, 14, 9, 4]

需要先建立一个maxHeap，透过起始点的公式(Math.floor(heapSize / 2))算出7，先从index 7 (数字12)开始，但因为12没有子节点，所以往index 6移动(数字7)，开始执行heapify
经过不断的heapify，最大值会移动到根节点
根节点与left node最右边的节点做交换，将最大值取出，移除left node最右边的节点
此时根节点并非最大值，需要再次进行步骤2，不断重复…
直到全部节点都取出，阵列就排序完成了

用js实作heap sort

const createMaxheap = (arr, heapSize) => {
    //从 Math.floor(heapSize / 2)这个节点开始检查
    for (let i = Math.floor(heapSize / 2); i >= 0; i--) {
        maxHeapify(arr, i, heapSize);
    }
};
const maxHeapify = (arr, i, heapSize) => {
    let largest;
    let left = i * 2 + 1; //取自己的左子节点
    let right = i * 2 + 2; //取自己的右子节点
    //检查subtree里面 谁是最大值?
    largest = left <= heapSize && arr[left] > arr[i] ? left : i;
    if (right <= heapSize && arr[right] > arr[largest]) {
        largest = right;
    }

    //如果subtree的parent不是最大的 就持续向下交换
    if (largest != i) {
        [arr[i], arr[largest]] = [arr[largest], arr[i]];
        maxHeapify(arr, largest, heapSize);
    }
};

const heapSort = (arr) => {
    let heapSize = arr.length - 1;
    //先建立maxHeap
    createMaxheap(arr, heapSize);
    for (let i = arr.length - 1; i >= 0; i--) {
        //将leaf node最右边那个跟根节点交换
        [arr[0], arr[i]] = [arr[i], arr[0]];
        //节点取出後 heapSize-1
        heapSize -= 1;
        //此时根节点并非最大值 需要执行maxHeapify
        maxHeapify(arr, 0, heapSize);
    }
    return arr;
};

heapSort([5, 13, 11, 8, 3, 15, 7, 12, 2, 16, 6, 10, 14, 9, 4]);

不得不说 heap sort是我觉得最难理解的排序演算法，需要反覆消化很多次才能理解