前言

堆排序需要将一颗完全二叉树构建成一个大顶堆或者小顶堆,然后将堆顶和最后的数字交交换

什么是大顶堆?
大顶堆

堆顶一定是最大值,父结点一定是三个值之间最大的值。小顶堆与其相反。
其中最大值为堆顶,第二层一定有一个次大值

二叉树的性质四

  • 具有n个节点的 完全二叉树 的深度为int(log_2n)+1 或者 math.ceil(log_2(n+1)) # log_2 对数的意思
  • int(math.log(n)) + 1

二叉树的性质五
如果有一颗n个结点的完全二叉树(深度为性质4).结点按照层序编号(i),如下:


        1
        
    2       3
    
  4   5   6   7
  
 8 9  10
  • 如果i=1,则结点i是二叉树的根,无双亲;
  • 如果i>1,则其双亲是int(i/2),向下取整。就是子节点的编号除以2得到的就是父结点的编号。
  • 父结点如果是i,那么左孩子结点就是2i,右孩子结点就是2i+1
  • 如果2i>n,则结点i无左孩子,即结点i为叶子结点;否则其左孩子结点存在编号为2i
  • n>2i 说明存在右孩子, 且标号为: 2i+1
  • 如果2i+1>n,则结点i右孩子,注意这里并不能说明结点i没有左孩子;否者右孩子结点存在编号为2i+1
  • 完全二叉树父亲结点一共有 n//2 个(包含根结点)

打印二叉树

构建大顶堆

        20
        
    40       50

构建单个二叉树

如上面的大顶堆,我们先判断改大顶堆是否有左孩子,然后判断右孩子
如果 有左孩子,我们假设左孩子是最大的那个树
然后判断是否有右孩子,如果有左孩子和右孩子比较,如果右孩子大于左孩子,保存右孩子为最大值
最后和父结点进行比较,如果大于父结点就交换位置,否则不变

代码实现

def max_heap(i, n, array):
    """
    调整数据为大顶堆
    :param i:   根节点的标号
    :param n:   结点个数
    :param array:   带构建的数据
    :return: list 构建好的大顶堆
    """
    while 2 * i <= n:
        # 性质五:如果2i>n,则结点i无左孩子
        # 这里表示有左孩子就进入循环
        l_index = 2 * i
        # 左孩子编号 2i
        max_index = l_index
        # 假设最大的就是左孩子,这里保存索引
        if 2 * i + 1 <= n and array[l_index] < array[2 * i + 1]:
            # 如果存在右孩子且右孩子大于左孩子,最大值索引为右孩子
            max_index = 2 * i + 1
        if array[max_index] > array[i]:
            # 最大值和根结点比较,如果最大值真的大于根节点,则交换位置
            array[max_index], array[i] = array[i], array[max_index]
            i = max_index
            # 修正i,继续向下调整直到不存在孩子结点
        else:
            # 没有孩子结点就退出循环
            break
    return array

全面调整二叉树为大顶堆

上面的算法从堆顶构建的话,不能达到我们的目的,但是从最后一个父结点开始就可以达到我们的目的
代码实现

def all_heap(total, array):
    """
    调整整个数据为大顶堆
    :param total: 结点个数
    :param array: 结点列表 
    :return: list
    """
    for i in range(total//2, 0, -1):
        # 父亲结点个数: 结点数 // 2
        max_heap(i, total, array)
        # 因为这里全是引用类型,没有拷贝数据。节省了内存空间
        # 从最后一个父结点开始调整
    return array

升序排序

未排序之前
第一次排序
将堆顶和最后一个交换,然后重新构建大顶堆
重新构建大顶堆
然后根系结点和最后一个结点进行交换

注意这里最后一个不是90,而是20, 90已经不再参与大顶堆构建

依次内推
代码实现


origin = [0, 30, 20, 80, 40, 50, 10, 60, 70, 90]
origin = all_heap(len(origin) - 1, origin)
# 构建大顶堆, 其实没有执行任何拷贝,直接调用函数就可以实现对origin的更改
def sort(total, array):
    """
    排序
    :param total: 结点个数
    :param array: 结点列表
    :return: list
    """
    while total > 1:
        array[total], array[1] = array[1], array[total]
        total -= 1
        max_heap(1, total, array)
        # 重构大顶堆,因为不要最后一个结点参与,所以total - 1
        if total == 2 and array[total] >= array[total - 1]:
            # 如果 标号为2的结点 大于或等于根节点就不做调整了
            break
    return array

到此,排序完成

始终注意list类型,如果不进行拷贝的话,不管怎么引用,他们都是表示的同一段内存空间,修改任何一个引用标识符相当于修改其他标识符的数据,如a = [1, 2], b = a, a.append(3), print(b) = > 1,2,3

最后修改:2020 年 07 月 15 日 03 : 26 PM
如果觉得我的文章对你有用,请随意赞赏