本文共 1089 字，大约阅读时间需要 3 分钟。

堆的向下调整

1. 啥是堆？

堆: 一种特殊的完全二叉树结构

堆分为大根堆、小根堆:

1. 大根堆: 一颗完全二叉树，满足任一节点都比其孩子节点大
   
2. 小根堆: 一颗完全二叉树，满足任一节点都比其孩子节点小
   

2. 堆的向下调整:

1. 什么是堆的向下调整?
   把不是堆的二叉树经过一个叫做【向下调整】的操作变为堆
2. 什么样的二叉树可以做向下调整?
   节点的左右子树都是堆，但自身不是堆的二叉树，比如:
   3. 怎么进行向下调整的操作?
   先看一张动图:
   

流程:

这样向下调整就结束了，一个二叉树就变为了堆！

3. 代码

'''TOPIC: 向下调整函数author: Bluetime: 2020-07-24e-mail: 2458682080@qq.com'''def sift(li, root, last):    """    :param li: 列表    :param root: 二叉树的根结点的下标    :param last: 二叉树的最后一个元素的下标    :return:    """    temp = li[root]   # 将根结点暂时储存起来    i = root  # i最开始指的是根结点    child = i * 2 + 1  # 先指向左孩子    while child <= last:   # 只要不到最后一个叶结点        if child+1 <= last and li[child+1] > li[child]:  #当右孩子>左孩子            child += 1  # 就把要换上去(要变为空位)的节点变为右孩子        if li[child] > temp:            li[i]  = li[child]            i = child  # 向下看一层            child = i * 2 + 1  # 继续指向左孩子        else:    # li[child] > temp 如果目前空位的最大的孩子都比tmep小，那temp就可以放这里            li[i] = temp            break     else:  # 当目前节点在叶结点时        li[i] = temp

这里输入的列表是把完全二叉树按照顺序存储方式储存在列表里，具体的可以看上一博文，左右孩子的寻找方式也在该博文中。

转载地址：http://hfiwi.baihongyu.com/