NB三人组之一——堆排序

要想了解堆排序，我们得先知道什么是树。

树是一种数据结构，而堆排序就是建立在这种数据结构上的一种算法。

我用图来让大家对数有个基本的认识。

我们再通过一张图来了解一下对于树的一些基本概念

•  根节点：A为根节点（像大树的根一样）
• 叶子节点：我们知道叶子是没有分支的，没有分支的节点称为叶子节点，这里面B C H I P Q K L M N 都为叶子节点。
  

  
  

• 树的深度（高度）：上图的深度为4，很好理解，就是看树最深有几层。
  

  
  

  ·

• 树的度：看树最多分了几个叉，上图中A分叉最多，分了7个叉，所以这个树的度为7.
• 父/孩子节点：顾名思义，上图中E为I的父节点，I为E的子节点。
  

  
  

• 子树：从大树中分出来的树为字数，上图中E I J P Q为一颗子树。
  

  
  

   

好啦，了解完树的概念，我们来了解一下什么叫做二叉树 ，依然用图来解释

 是不是很好理解呢(●'◡'●)

接下来我们来了解一下完全二叉树和满二叉树

 其实树的名字起的名字都挺简单易懂不需要死记硬背 看名字意思便知啦

---

堆：一种特殊的完全二叉树 只能是大根堆或小根堆
大根堆：一颗完全二叉树，满足任一节点都比其孩子节点大
小根堆：一颗完全二叉树，满足任一节点都比其孩子节点小

---

有人可能会有疑问，Python中没学过树的存储方式啊。

其实树的存储方式为列表存储。

 上面这张图即是树的存储方式。

其中子节点与父节点的关系很重要，左节点: i-->2i+1，右节点:

i-->2i+2,这是我们 *** 作树的重要依据。

---

上面我们提到堆只能是一种大根堆或小根堆，但我们存储数据并不是直接就是有顺序排列的，所以我们要堆树进行向下调整

堆的向下调整：
假设根节点的左右子树都是堆，但根节点不满足堆的性质
可以通过一次向下的调整来将其变成一个堆

注意只有堆顶不满足堆的性质，意思只有堆顶不符合顺序，所以我们把堆顶放在合适的位置。

下面我们用代码实现它。

​​def sift(lst,low,high):
    """
    :param lst: 列表
    :param low: 堆的根节点位置
    :param high: 堆的最后一个元素位置
    :return:
    """
    i=low
    j=2*i+1     # 从父节点找子节点（左）
    temp=lst[low] #把堆顶存起来
    while j<=high: #只要j位置有数
        if lst[j+1]>lst[j] and j+1<=high : #右孩子比左孩子大走向右边 得保证右孩子有
            j=j+1 # j指向右孩子
        if lst[j]>temp:
            lst[i]=lst[j]
            i=j              #往下看一层
            j=2*i+1
        else:         #tmp更大 把tmp放到i的位置
            lst[i]=temp
            break
    else: # i到最后一层
        lst[i]=temp

假设我们要对一个大根堆进行调整。

我们用i代表父节点，j代表子节点，用temp存储根节点。

这时我们用到了上面提到的父节点和子节点的关系：j = i*2+1,我们首先要比较左右孩子节点决定根节点的走向,如果右孩子节点比左孩子节点大，那么肯定右孩子节点比左孩子节点更有资格作为它的父节点。

比较完后我们把孩子节点与temp进行比较如果比temp比较如果比temp大，自然lst[ j ]可以作为temp的父节点所以lst[ i ]=lst[ j ],这是lst[ i ]的位置空下所以我们将i,j同时往下移找temp合适的位置。

如果子节点比temp小，所以temp可以作为lst[ j ]的节点。

 注意high代表树的最后一个叶子节点，也是树的边界，当 i>high 时说明 i 遍历到树的最后一层了，也代表temp比所有节点都小，temp放在最后一层。

我们来用图来解释一下这个过程

这是一开始的堆，只有堆顶有问题

 此时 i 指向父节点 j 指向子节点与temp（16）比较 52比16大所以52作为父节点

下面 i 指向52（已空出）的位置 j 指向41（41比28大）

 

 lst[ j ]与temp做比较

 41比temp大所以将lst[ j ]赋值给lst [ i ]，下面 i 指向41（已空出）的位置 j 指向15的位置，temp比15大所以将temp赋值给lst[ i ]，向下调整结束。

---

接下来我们来实现堆排序。

先给大家用代码实现我再来解释。

​
def heap_sort(lst):
    '建堆过程'
    n=len(lst)
    '遍历每一个小堆的根节点 进行调整'
    for i in range((len(lst)-1-1)//2,-1,-1):    # i为建堆时从下到上的跟的下标
        '使用sift 调整'
        sift(lst,i,len(lst)-1) # 这里high等于最后一个数依然起到防止越界的功能
    # 堆建立完成
    '''挨个出数'''
    for i in range(n-1,-1,-1):
        '''上面的数跟下面的数做交换'''
        lst[0],lst[i]=lst[i],lst[0]
        sift(lst,0,i-1) # i-1是新的最下端

​

实现堆排序说起来很简单，1.建立一个堆，2.对堆进行挨个出数

如何建立堆呢？这时就要用一下我们的向下调整函数，还记得树的每一个小分枝也是一个树嘛。

我们把一个大树用每一个根节点分成小堆，进行向下调整就可以啦，我用图来解释一下。

 第一个小堆为[ 3，5],第二个小堆为[ 9，2 ，4]，第三个小堆为[ 1，0，7]，第四个小堆为[ 8，9，3，2，4，5]，最后为整个树。

对这个几个小堆分别进行向下调整即可，现在的问题就是解决根节点下标的问题，len( lst )-1代表最后一个叶子节点再-1整除2 既是子节点对应的父节点，因为是整除所以不存在左右节点的问题。

通过for循环即可以遍历每个根节点，使用snif函数（向下调整）即可。

注意for循环中的high依然是len( lst )-1 也可以起到限制作用。

我们进行第二步，挨个出数。

 我们发现堆从顶到堆底的顺序并不是我们想要的排序，我们可以这样想，从最后一个子节点向前与堆顶互换位置，再对除了以交换位置的堆的堆顶进行向下调整，这样堆顶一直是最大数，一直与新堆底进行位置交换，这样我们就将堆变成了我们想要的顺序啦。

---

下面我们来讨论堆排序的时间复杂度

堆排序的时间复杂度为O（nlogn）

🌸🌸🌸🌸🌸🌸完结撒花！🌸🌸🌸🌸🌸🌸

如有疑问或错误，欢迎大家评论区留言指出，谢谢支持！！