堆的原理以及实现

堆的原理以及实现
本文是在好友哆啦奇梦的耐心指导下完成的，在此表示感谢！

1. 大顶堆：
   所有的父节点的值都比孩子节点大，叶子节点值最小。root 根节点是第一个节点值最大

2. 小顶堆：
   和大顶堆相反，所有父节点值，都小于子节点值，root 根节点是 第一个节点值最小

根据完全二叉树的性质，若将堆中的数据至顶向下，从左向右的存在一个一维数组里面，
则父节点的位置索引总是该节点位置索引减1再除2取整的结果。 p = (c-1) // 2

---

下面的图片来自这里
堆的列表索引对应的形状如下：

维护一个堆主要有两个操作：上浮和下沉：
如果是维护一个最小堆，上浮操作如下,子节点找他的父节点，如果子节点小于父节点，那么我们就交换父子节点的值

同上，如果是维护一个最小堆，我们的父节点比子节点大，就需要下沉。下沉的操作如下：

实现的代码如下：

from typing import List
"""
父节点与子节点的索引位置关系，p父节点，c子节点
p = (c-1)//2
c1 = 2*p+1
c2 = 2*p+2
本程序维护的是一个最大堆
"""

#对某一个父节点进行下沉，用于删除堆顶元数  arr数组；p节点；arr_len：数组长度
def downAdjust(arr, p, arr_len):
    temp = arr[p]#找到要下沉的父节点的值
    c = 2*p + 1 #计算出其左子节点的索引
	#最大堆降序排序
    while c <= arr_len:#当索引的位置在数组内的时候
        if (c+1) <= arr_len and arr[c] > arr[c+1]:#当前儿子比另一个儿子大
            c += 1#找到父节点的两个儿子中的较小的那一个
        if temp <= arr[c]:#如果父节点小于等于小儿子，不对，弹出，不能下沉
            break
        arr[p] = arr[c]#父节点值变成小儿子的值
        p = c#父节点的索引变成小儿子的索引
        c = 2*p+1
    arr[p] = temp
    return arr
    """最小堆升序排序
    while c <= arr_len:#当索引的位置在数组内的时候
        if (c+1) <= arr_len and arr[c] < arr[c+1]:#当前儿子比另一个儿子大
            c += 1#找到父节点的两个儿子中的较大的那一个
        if temp >= arr[c]:#如果父节点大于等于大儿子，不对，弹出，不能下沉
            break
        arr[p] = arr[c]#父节点值变成大儿子的值
        p = c#父节点的索引变成大儿子的索引
        c = 2*p+1
    arr[p] = temp
    return arr
    """
#对某一个节点'上浮' 在插入的时候,把新节点插入到完全二叉树的最后一个位置
def upAdjust(arr, length):
    c = length - 1#子节点
    p = (c-1) // 2#父节点
    temp = arr[c]#临时保存子节点
    
    while c > 0 and temp > arr[p]:#子节点存在且比父节点大
        arr[c] = arr[p]
        arr[p] = temp
        c = p
        p = (c-1)//2
    #弹出的时候，子节点小于等于其父节点的值的时候，填充上浮的值到正确的位置
    arr[c] = temp
    return arr

#构建一个最大二叉堆
def buildHeap(arr):
    n = len(arr) - 1#算出数组的长度
    p = (n-1) // 2#计算出倒数的父节点

    while p >= 0:
        arr = downAdjust(arr, p, n)
        p -= 1
    return arr

#堆排序
def heapSort(arr):
    buildHeap(arr)
    n = len(arr) - 1
    for i in range(n, 0, -1):
        arr[i], arr[0] = arr[0],arr[i]
        arr = downAdjust(arr, 0, i-1)
    return arr

来看一个建立最大堆的例子：输入为[1,3,5,2,4,]


说明
为啥开始建立的是最小堆，然后继续使用下沉就变成了最大堆的排序？？

• 建立最小堆之后，列表第一个元素是最小的，
• 使其与列表最后一个较大的元素交换，那么列表的最后一个元数就是最小值了。
• 我们在使用下沉，但是这里的下沉范围为 n - 1，意思就是最后一个最小的元素已经排好序，不参与下沉。
• 我们再对前面的n-1个数进行一个下沉取最小堆的操作，得到n-1个数的最小堆，堆顶的元数是这n-1中最小的。
• 重复上述的倒数第二个元数和堆顶的最小元数交换，然后下沉的区间长度又减一，重复下去，我们就可以得到一个，排序的最大堆。

注意
我们刚才是通过求最小堆来得到一个最大堆得排序。我们如果想要得到得一个最小堆得排序，也是和上面得操作类似。只要我们开始的时候得到的是一个最大堆，每次交换堆顶和堆底的值，就可以得到一个排序的最小堆。

---

建立最大堆和最小堆的区别与联系：
我们在下沉建立堆的时候，例如上述的代码，建立一个最小堆的时候(非严格排序)。

我们每次的父节点比较的对象是小儿子，如果父节点大于小儿子，那么父节点就赋值为小儿子的值。然后小儿子作为父节点，找到小孙子，如果小儿子大于小孙子，那么小儿子就变成小孙子。最后弹出之后，小孙子赋值成为爷爷，即对这一条链路进行递增排序，最大的放在后面，所以可以下沉形成一个最小堆。

def downAdjust(arr, p, arr_len):
    temp = arr[p]#找到要下沉的父节点的值
    c = 2*p + 1 #计算出其左子节点的索引
	#最大堆降序排序
    while c <= arr_len:#当索引的位置在数组内的时候
        if (c+1) <= arr_len and arr[c] > arr[c+1]:#当前儿子比另一个儿子大
            c += 1#找到父节点的两个儿子中的较小的那一个
        if temp <= arr[c]:#如果父节点小于等于小儿子，不对，弹出，不能下沉
            break
        arr[p] = arr[c]#父节点值变成小儿子的值
        p = c#父节点的索引变成小儿子的索引
        c = 2*p+1
    arr[p] = temp
    return arr

所以我们在建立一个最大堆的时候，需要修改上述的比较条件。由于最大堆是大的在前面，所以这次的爷爷节点值应该是要和大儿子的比较，如果爷爷节点值大于大儿子的值，说明是这次循环是已经排序好了的。但是如果爷爷节点值小于大儿子的值，这时候大儿子的值就要赋值给爷爷节点，大儿子作为新的父节点，去和大孙子节点比较，如果大儿子节点值小于大孙子节点值，大儿子节点被赋值为大孙子节点值。弹出的时候，大孙子节点值被赋值为这三代中最小的那个爷爷节点值。就此完成一个小循环最小堆的建立。

    while c <= arr_len:#当索引的位置在数组内的时候
        if (c+1) <= arr_len and arr[c] < arr[c+1]:#当前儿子比另一个儿子大
            c += 1#找到父节点的两个儿子中的较大的那一个
        if temp >= arr[c]:#如果父节点大于等于大儿子，不对，弹出，不能下沉
            break
        arr[p] = arr[c]#父节点值变成大儿子的值
        p = c#父节点的索引变成大儿子的索引
        c = 2*p+1
    arr[p] = temp
    return arr