【常考排序算法】堆排序

1. 思路

Heap特点：

是一颗完全二叉树
父节点 > 子节点（左右子节点大小顺序随意）

堆排序流程：

buildMaxHeap：把一个无序的数组，排成最大堆（即父节点总比子节点小），这个建堆的过程称之为 heapify。从最后一个非叶节点开始向前遍历，即从第 $i = (l a s t N o d e - 1) / / 2 = (l e n (a r r) - 2) / / 2$ (整除向下取整)个节点逆序从下往上进行 heapify 的操作，即下图 $i = 3$ 开始，即。（其实这里从 $i = (l e n (a r r) - 1) / / 2$ 也是可以的，就是从下图的 $i = 4$ 开始的，第一次操作由于越界会直接略过）参考下图：
HeapSort: 第一步建完堆以后，最大的数在最顶上的节点（ $i = 0$ ）。从最后一个节点开始，至下而上操作
1）把最后一个节点与最顶上的节点交换（最大的数从堆顶 $i = 0$ 跑到最后 $i = (l e n (a r r) - 1)$ ）
2）拿出最后一个元素（从原堆中砍断出来），这就是最大的元素，这样堆就被打乱了
3）重新恢复最大堆，对最顶上的元素再做 heapify，下面如果还是乱的，则递归进行，即可恢复

2. 代码

"""【堆排序】 https://www.bilibili.com/video/av47196993?from=search&seid=4351042127032790802 1. 在最大堆的基础上（根节点的数字大于任意子节点），属于完全二叉树，最大的值是在最顶上的根节点上的 2. 把最大的（最顶上的）节点和最末尾的一节点交换，即最大的节点跑到了最后一位，而后把最后一位砍断 3. 因为上一步做过交换以后肯定破坏了堆得结构，所以对最顶上的一对父子节点进行heapify，即把父节点和最大的子节点交换 交换之后，最顶上的那一对父子节点又成为堆，（尽管底下不一定是堆，但是所有之中最大的数一定是位于最顶上的） 4. 重复第2步，循环 """
""" parent = (i-1) / 2 child_1(c1) = 2i + 1 child_1(c2) = 2i + 2 """

def swap(arr, i, j):
    temp = arr[i]
    arr[i] = arr[j]
    arr[j] = temp

def heapify(tree, n, i):
    """ 把父节点和最大的子节点交换(父节点和两个子节点依次判断，找出最大，而后调换) :param n: 总共的节点数 :param i: 元素的索引，对第 i 个元素做 heapify i / \ c1 c2 """
    # if i >= n: # 递归出口 0 <= i <= (n-1)，但是由于并不会越界，此处不需要递归出口
    # return

    c1 = 2 * i + 1  # 左边子节点
    c2 = 2 * i + 2  # 右边子节点
    # 找出父节点&两个子节点中的最大节点
    max = i   # 先假设最大值为父节点
    if c1 < n and tree[c1] > tree[max]:
        max = c1
    if c2 < n and tree[c2] > tree[max]:
        max = c2
    if max != i:                  # 只要执行了上面两个if之一，即交换了下标，就会出现max != i的情况，才需要交换
        swap(tree, max, i)        # 如果上面交换了下标，这里则交换值
        heapify(tree, n, max)   # 递归 如果原先是max那个节点，那么这里会被调换过，也就是比较大的值被拿到父节点，换来了一个比较小的数，所以需要往下递归下去

def build_heap(tree, n):
    """ 建立一棵树 """
    # last_node = n - 1 # 最后一个节点
    # parent = (last_node - 1) // 2 # 最后一个节点对应的父节点, // 表示向下取整

    parent = (n - 2) // 2  # 最后一个节点对应的父节点, // 表示向下取整 , 其实
    for i in range(parent, -1, -1): # range(start, end, step) 不包含 end 本身
        print("i:",i)
        heapify(tree, n, i)

def heap_sort(tree, n):
    build_heap(tree,  n)
    for j in range(n-1, -1, -1):
        swap(tree, j, 0)         # 每次都把最后一个节点和最顶上的节点交换
        # 拿出（砍断）最后一个节点（上一步交换完后最大的数已经在最后了），而后从最顶上节点开始 heapify，又往下递归，直到形成稳定堆
        # 此处 heapify的参数是 i 而不是 n，因为不断砍断以后，整个数组长度从 n 变成了 i
        heapify(tree, j,  0)



if __name__ == '__main__':

    tree = [10, 5, 8, 3, 4, 6, 7, 1, 2]   # 把二叉树从上到下，从左到右打出来

    n = len(tree)
    #heapify(tree, n, 0)
    heap_sort(tree, n)
    print("tree:", tree)