一、树相关知识
- 树的深度(高度)：表示树最深有几层
- 树的度：每个节点的分叉数量叫度，所有节点中分叉数量最多的是树的度
- 二叉树：度不超过2的树（每个节点最多有两个分叉)
-
完全二叉树：叶子节点只能出现在最下层和次下层，如果从树根开始按序编号中间没有遗漏就是完全二叉树
- 满二叉树：每一层的节点都占满。也是完全二叉树
完全二叉树的存储
使用列表方式存储，必须存储完全二叉树
li = [8,4,12,2,6,10,14,1,3,5]#对应下标[0,1,2,3,4,5,6,7,8,9]
基于下标，父节点找左孩子节点：
i -> 2i+1
基于下标，父节点找右孩子节点：
i -> 2i+2基于下标，左孩子找父节点：
i-> (i-1)/2
基于下标，右孩子找父节点：
i-> (i-2)/2
孩子找父节点可以合并为：i->(i-1)//2
二、堆的基本概念
堆是一种完全二叉树
-
大根堆：任意节点都比孩子节点大
-
小根堆：任意节点都比孩子节点小
堆的向下调整性
根节点的左右子树都是堆，根节点所在的树自身不是堆。可以通过一次向下调整变成一个堆。
原图
调整后的图
三、堆排序
构造大根堆
从最后一个有孩子的节点，以该节点为根的树如果满足大根堆不做调整。如果不是大根堆，则利用向下调整性构造一个大根堆。
5,4,2,7,0都没有子节点，单个节点本身就是一个堆，所以从3开始
原图
构造大根堆
挨个出数
由于是大根堆，取出的根元素是最大的值。图示第一次取跟元素，取出后剩余元素重新排序，发现最终得到的不是一个完全二叉树，该方法不符合要求。因为堆必须是一个完全二叉树。
为了得到一个完全二叉树，当取出根元素后，可以利用树的最后一个元素顶替上去，再利用向下调整性重新排序后取出根元素，不断重复。每次取的根元素排列得到升序的结果，即实现了堆排序。
代码实现
def sift(li,low,high):#堆的向下调整性
tmp = li[low]
i = low
j = 2 * i + 1
while j <= high:#第二种情况：i指向叶子节点，j指向值已经超出high范围
if j + 1 <= high and li[j+1] > li[j]:#j指向左右两个节点值最大的位置
j += 1
if li[j] > tmp:
li[i] = li[j]
i = j
j = 2 * i + 1
else:#第一种情况：左右两个子节点都比tmp大
break
li[i] = tmp
def heap_sort(li):
n = len(li)
#构造堆
for low in range(n//2 - 1,-1,-1):#最后一个节点是n-1,找到父节点n//2 - 1,然后一直到0的位置构造堆
sift(li,low,n-1)#使用整个数的最大下标n-1作为每个子树的high,简单且不影响第二种情况判断
#挨个出数
for high in range(n-1,-1,-1):#n-1下标到0
li[0],li[high] = li[high],li[0]#当前范围的根元素和high指向的元素换位置
sift(li,0,high-1)#交换后修改high的位置后再重新调整
向下调整性两种退出循环情况演示：
原图
第一种终止情况.gif
第二种终止情况.gif
时间复杂度
def heap_sort(li):
...
for low in range(n//2 - 1,-1,-1): #O(n)
sift(li,low,n-1) #由于while循环中j = 2 * i + 1，所以是O(logn)
for high in range(n-1,-1,-1): #O(n)
li[0],li[high] = li[high],li[0] #O(1)
sift(li,0,high-1) #O(log(n))
时间复杂度是：O(n*logn)
内置模块实现
- 内置模块只能构造小根堆
import heapq
li = [0,6,2,7,5,8,3,1]
heapq.heapify(li)#内置方法构造的是小根堆
print(li)#[0, 1, 2, 6, 5, 8, 3, 7]
heapq.heappush(li,9)#插入一个元素，重新构造堆
print(li)#[0, 1, 2, 6, 5, 8, 3, 7, 9]
item = heapq.heappop(li)#小根堆根元素出来最小的值,剩下的重新构造堆
print(item)#0
print(li)#[1, 5, 2, 6, 9, 8, 3, 7]
- heappop()挨个出数实现排序
import heapq
li = [0,6,2,7,5,8,3,1]
heapq.heapify(li)
res = [heapq.heappop(li) for i in range(len(li))]
print(res)
>>>[0, 1, 2, 3, 5, 6, 7, 8]
