一、树与二叉树简介
- 树是一种数据结构 比如：目录结构
- 树是一种可以递归定义的数据结构
- 树是由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）
