堆积排序法(Heap Sort)笔记

记录学习内容。看网路上大大们的文章和影片，做些纪录。
以下内容大多来自网路上大大们的文章。
还不了解，内容可能有错误。

之前有纪录排序的程序来源，现在学习排序的一些观念
java，quicksort、Counting Sort和c++ ，mergesort、Heap Sort和 js ，Shell Sort、Radix Sort
https://ithelp.ithome.com.tw/articles/10219345

[演算法] 排序演算法(Sort Algorithm)
http://notepad.yehyeh.net/Content/Algorithm/Sort/Sort.php

堆积排序法(Heap Sort)

堆积排序法(Heap Sort) 分为两种:

最小堆积(Min Heap)：父节点的值 < 子节点的值
Root 会是最小值。

最大堆积(Max Heap)：父节点的值 > 子节点的值。
Root 会是最大值

Max Heap 排序方法 :

步骤 1 : 
将Complete Binary Tree 的 阵列 转成 Max Heap 。

步骤2 : 
因为 root 是最大值 ，所以Max Heap 排序 ，就是不断把root拿出来。

把root拿出来的方法 : 把root 和 最後一个节点(阵列最後一项) 交换 。

所以 最後面 就会是 数列的最大值 。

但交换後 ，Max Heap  又会乱掉 ， 所以把 剩余阵列 转成 Max Heap (忽略最後一项，因为不断把root 丢到最後面 ，後面数列会是排序好的结果，所以忽略) 。

总结:
建Max Heap
去root
建Max Heap
去root
建Max Heap
去root

次数: 阵列个数-1

Min Heap 排序方法 :

步骤 1 : 
将Complete Binary Tree 的 阵列 转成 Min Heap 。

步骤2 : 
因为 root 是最小值 ，所以Min Heap 排序 ，就是不断把root拿出来。

把root拿出来的方法 : 把root 和 最後一个节点(阵列最後一项) 交换 。

所以 最後面 就会是 数列的最小值 。

但交换後 ，Min Heap  又会乱掉 ， 所以把 剩余阵列 转成 Min Heap (忽略最後一项，因为不断把root 丢到最後面 ，後面数列会是排序好的结果，所以忽略) 。

总结:
建Min Heap
去root
建Min Heap
去root
建Min Heap
去root
次数: 阵列个数- 1

Min Heap排序、Max Heap排序不同的地方在哪 ?

Max heap 可以从阵列最後面 依序 放最大值:
n ，n-1， n-2

Min heap 只能把每次的 最小值 放到第 n 个位置 ，这样最後才会是从小到大 。

所以Min heap 如果没特别改变写法的话 ，root从n ，n-1， n-2 这样放的话，
排序 会是由大到小 。

来看程序:
HeapSort
https://www.geeksforgeeks.org/heap-sort/
Heap Sort | GeeksforGeeks
https://www.youtube.com/watch?v=MtQL_ll5KhQ&ab_channel=GeeksforGeeks

程序大概都是 : MaxHeap 的 sort 从小到大。

建立heap的function 通常取名为 Heapify( Heapify 是指每一步骤，不过先这样记吧) :

heapify有3个参数

    void heapify(int arr[], int n, int i) {

    }
arr[] 就是阵列 ，整个数列 。
n 是 MaxHeap的 个数 ，因为会不断地把最大值往右搬 ， 所以MaxHeap的 个数 会不断-1-1
i 是要调整的节点(阵列的索引值) 。

heapify方法里的内容 :

i 是现在想调整的节点
int l = 2*i + 1; // left = 2*i + 1 
int r = 2*i + 2; // right = 2*i + 2 

2*i + 1 是 i的左节点
2*i + 2 是 i的右节点

这三个数字 ，看谁最大 。

如果 最大的是i ，就不用调整 ，因为MaxHeap本来就要root 是这三者中最大的 。

如果是左节点，或右节点 比较大 ，就跟i交换 。

交换後 ， 代表 原本在i索引的地方 ，变成左节点或右节点 的值

代表 原本在 左节点或右节点 索引的地方 ，变成 i索引 的值

原本在 左节点或右节点 索引的地方 这边 写为 largest(三者中最大值) 索引 。

largest索引 要再继续跑heapify 。因为不确定largest 索引 是不是root ，如果是root ，还要继续 跟左右节点 比谁大 。

看完heapify 後，来看主程序sort :

步骤是:

建Max Heap
去root
建Max Heap
去root
建Max Heap
去root

一开始建MaxHeap ，就是把每个parent节点，去跑heapify ，确保每个parent节点都是三者之中最大值。

        // Build heap (rearrange array) 
        for (int i = n / 2 - 1; i >= 0; i--) 
            heapify(arr, n, i);

如图，索引有0到4
所以i 是 4/2-1 = 1
先检查索引1底下是不是MaxHeap 。再检查索引0底下是不是 MaxHeap

MaxHeap 还有另一种建立方法

如果数列12345678 ， 就从1 ，1、2， 1、2、3 ，这样一个一个加入MaxHeap ，每加入一个数字，那个数字就要不断往上跟root 比，改成MaxHeap ，时间复杂度是 n * logn
m 代表有几个节点
log n 代表 往上比

如图，4

参考:
Why is the top down approach of heap construction less efficient than bottom up even though its order of growth is lower O(log n) over O(n)?
https://stackoverflow.com/questions/36226714/why-is-the-top-down-approach-of-heap-construction-less-efficient-than-bottom-up

这种方法是top down(root往下) ，程序里的是bottom up(根往上)

程序里的建立MaxHeap的时间复杂度是 Ο(n)

       // Build heap (rearrange array) 
        for (int i = n / 2 - 1; i >= 0; i--) 
            heapify(arr, n, i);

直觉记法(错误记法?):因为从 最後一个parent节点 ，不断往上面的parent跑 。
每个节点 大概走过一次 ，所以是 n 。

看这部教学:
Algorithms lecture 13-- Build max heap algorithm and analysis
https://www.youtube.com/watch?v=HI97KDV23Ig&ab_channel=GateLecturesbyRavindrababuRavula

这样的想法应该不太正确:

直觉记法:因为从 最後一个parent节点 ，不断往上面的parent跑 。
每个节点 大概走过一次 ，所以是 n 。

教学里的解答是 :

高度0 -- >叶子 的heapify ，不用执行 ，时间复杂度O(0)

高度1-- >heapify 1层，时间复杂度O(1)

高度2 -- > heapify 2层，时间复杂度O(2)

高度3 -- > heapify 3层，时间复杂度O(3)

高度logn - > heapify  logn层，时间复杂度O(logn)

时间复杂度 : 每一层的节点个数 * heapify  的总和 。

总之最後结果是 O(n) ，看不懂证明 。