【算法】二叉树(满二叉树和完全二叉树)、堆(堆的向下调整)、堆排序、堆的内置模块heapq
1 二叉树
1.1 满二叉树和完全二叉树
1.2 堆的向下调整
2 堆排序
3 堆的内置模块
1 二叉树
二叉树是一种树形数据结构，其中每个节点最多有两个子节点，分别称为左子节点和右子节点。二叉树的常见类型包括：
1. **普通二叉树**：任意一种二叉树，没有特定的性质约束。
2. **完全二叉树**：除了最后一层，其他层的节点都是满的，且最后一层的节点尽可能向左排列。
3. **满二叉树**：每一层的节点数都达到最大值，即每个节点要么有两个子节点，要么没有子节点。
4. **平衡二叉树（AVL树）**：一种自平衡的二叉搜索树，任何节点的两个子树的高度差不超过1。
5. **二叉搜索树（BST）**：对于每个节点，左子节点的值小于该节点的值，右子节点的值大于该节点的值。
6. **红黑树**：一种特殊的二叉搜索树，通过额外的“红”或“黑”标记来保持树的平衡，使得最长路径不超过最短路径的两倍。这些二叉树类型在算法和数据结构中用于实现高效的搜索、排序和数据管理操作。
1.1 满二叉树和完全二叉树
1.2 堆的向下调整
向下调整为下图注意观察树的变化
2 堆排序
"""
满二叉树：一个二叉树，如果每一个层的结点数都达到最大值，则这个二叉树就是满二叉树。
完全二叉树：叶节点只能出现在最下层的次下层，并且最下面一层的结点都集中在该层最左边的若干位置的二叉树。二叉树的存储方式：链式存储方式顺序存储方式堆：一种特殊的完全二叉树堆排序（Heap Sort）是一种基于堆数据结构的比较排序算法，具有优良的时间复杂度表现。
堆是一种特殊的完全二叉树结构，可以分为两种类型：
最大堆：每个节点的值都大于或等于其子节点的值。
最小堆：每个节点的值都小于或等于其子节点的值。堆排序通常使用最大堆来进行排序。
其基本步骤如下：
步骤1：构建最大堆首先，将待排序数组构建成最大堆。这一步的目的是将数组中的最大元素移动到根节点（即数组的第一个位置）。
步骤2：交换堆顶元素和最后一个元素将堆顶（最大元素）与堆的最后一个元素交换，然后将堆的大小减一，排除最后一个元素，因为它已经处于正确的位置。
步骤3：调整堆对堆顶元素进行调整，使剩余的元素仍然保持最大堆的性质。这个过程通常称为“堆化”或“下沉”。
步骤4：重复步骤2和步骤3重复步骤2和步骤3，直到所有元素都排好序。时间复杂度堆排序的时间复杂度为 O(nlogn)，其中 n 是待排序元素的数量。它在最坏、最好和平均情况下的时间复杂度都是 O(nlogn)，并且它是一种不稳定的排序算法。
"""def sift(li: list, low: int, high: int):""":param li:列表:param low:堆的根节点位置:param high:堆的最后一个元素的位置:return:"""i = low # i最开始指向根节点j = 2 * i + 1 # j开始是左孩子tmp = li[low] # 把堆顶存起来while j <= high: # 只要j位置有数if j + 1 <= high and li[j + 1] > li[j]: # 如果右孩子有并且比较大j = j + 1 # j指向右孩子if li[j] > tmp:li[i] = li[j]i = j # 往下看一层j = 2 * i + 1else: # tmp更大，把tmp放到i的位置上li[i] = tmp # 把tmp放到某一级领导位置上breakelse:li[i] = tmp # 把tmp放到叶子节点上def heap_sort(li: list):n = len(li)for i in range((n - 2) // 2, -1, -1):# i表示建堆的时候调整的部分的根的下标sift(li, i, n - 1)# 建堆完成了print(li)for i in range(n - 1, -1, -1):# i 指向当前堆的最后一个元素li[0], li[i] = li[i], li[0]sift(li, 0, i - 1) # i-1是新的highli = [i for i in range(100)]
import randomrandom.shuffle(li)
print(li)
heap_sort(li)
print(li)
3 堆的内置模块
import heapq # q->queue 优先队列
import randomli = list(range(100))
random.shuffle(li)print(li)heapq.heapify(li) # 建堆n = len(li)
for i in range(n):print(heapq.heappop(li), end=',')