Python 算法 | 堆排序

一、树与二叉树简介

• 树是一种数据结构 比如：目录结构
• 树是一种可以递归定义的数据结构
• 树是由n个节点组成的集合：
  • 如果n=0，那这是一棵空树；
  • 如果n>0，那存在1个节点作为树的根节点，其他节点可以分为m个集合，每个集合本身又是一棵树；

特殊且常用的树——二叉树
二叉树：度不超过2的树（节点最多有两个叉）

两种特殊二叉树

• 满二叉树：一个二叉树，如果每一个层的结点数都达到最大值，则这个二叉树就是满二叉树；
• 完全二叉树：叶节点只能出现在最下层和次下层，并且最下面一层的结点都集中在该层最左边的若干位置的二叉树；

二叉树的存储方式

• 链式存储方式
• 顺序存储方式（列表）

父节点和左孩子节点的编号下标有什么关系？
i = 2i+1

父节点和右孩子节点的编号下标有什么关系？
i = 2i+2

找一个节点的父节点
（i-1）//2

（完全）二叉树可以用列表来存储，通过规律可以从父亲找到孩子或从孩子找到父亲;

二、堆

• 大根堆：一棵完全二叉树，满足任一节点都比其孩子节点大（也叫大顶堆）；
• 小根堆：一棵完全二叉树，满足任一节点都比其孩子节点小（也叫小顶堆）；

大根堆
小根堆

1.堆的向下调整性质 （构造子堆）

前提：节点的左右子树都是堆，但自身不是堆。
方法：当根节点的左右子树都是堆时，可以通过一次向下的调整来将其变换成一个堆。

分析：
（1）2的左右都是堆，但是2放在这里有点违和。

（2） 需要开始不断调整2的位置，发现把9,8,6逐个向上调，最后将2放到最下面最为合适

2.构造堆（各个小分支内，利用堆的向下调整性质构造分支堆，最后就构成一个大堆）

首先，从堆的最后一个叶子（high）来找，看看high叶子和父节点谁大。然后替换。

image image

然后，依次往前按照此方法处理其他分支

3. 堆排序过程

• 建立堆，得到堆顶元素，为最大元素；
• 去掉堆顶，将堆最后一个元素放到堆顶，此时可通过一次调整重新使堆有序。 堆顶元素为第二大元素；
• 重复步骤2，直到堆变空；

完整代码

import random

def sift(li, low, high):                        # li表示树, low表示树根, high表示树最后一个节点的位置
    tmp = li[low]
    i = low
    j = 2 * i + 1                               # 初识j指向空位的左孩子
    # i指向空位,j指向两个孩子
    while j <= high:                            # 循环退出的第二种情况: j>high,说明空位i是叶子节点
        if j + 1 <= high and li[j] < li[j+1]:   #如果右孩子存在, 并且比左孩子大,指向右孩子
            j += 1
        if li[j] > tmp:
            li[i] = li[j]
            i = j
            j = 2 * i + 1
        else:                                   # 循环退出的第一种情况:j位置的值比tmp小,说明两个孩子都比tmp小
            break
    li[i] = tmp


def heap_sort(li):
    n = len(li)
    # 1. 构造堆
    for low in range(n//2-1, -1, -1):
        sift(li, low, n-1)
    # 2. 挨个出数
    for high in range(n-1, -1, -1):
        li[0], li[high] = li[high], li[0] # 退休 棋子
        sift(li, 0, high-1)

li = list(range(100000))
random.shuffle(li)
heap_sort(li)

时间复杂度：O（nlogn）