堆
堆结构非常重要
优先级列表
把一个数组理解成一个完全二叉树（脑补）
- 堆结构的heapInsert与heapify
- 堆结构的增大和减少
- 如果只是建立堆的过程，时间复杂度为O(N)
- 优先级队列结构，就是堆结构
二叉树
在不越界的情况下，第 i个元素：
- 左节点：2 * i + 1
- 右节点：2 * i + 2
- 父节点：(i - 1) / 2（0号元素的父节点还是0，-1/2 = 0）
完全二叉树
- 满二叉树：任何一个非叶节点，一定有左节点和右节点
- 不是满二叉树：所有节点，
从左到右依次补齐
大根堆
任何一棵子树的最大值，都是这棵子树的头部
小根堆
任何一棵子树的最小值，都是这棵子树的头部
生成堆
headInsert
一个新节点加入堆中，同时这个节点向上调整的过程
- 新进来一个节点，它只可能和H个元素比较：H==>
完全二叉树的高度：O(logN) - 建立大根堆的过程
- 时间复杂度：O(N)==> log1 + log2 + log3 …
heapify
堆中有一个值（X）发生变化了，怎么调整才能让这个堆仍然是大根堆
- 找到X的左节点和右节点，较大的值（M）和X比较
- 如果X < M：X和M交换
示例
有一个流，不断在吐出数（无序），随时找到流中的中位数
可行方案
- 方案一
- 用一个数组装这些数（O(1)）
- 每次需要中位数的时候，对数组排序（O(NlogN)）
- 取出中位数
- 方案二
- 使用两个数组（大根堆、小根堆），较小的N/2个都放在大根堆中，较大的N/2都放在小根堆中
- 当两个数组的长度大于1的时候，从多的数组中，减堆（
弹出大根堆/小根堆的堆顶），放到少的数组中- 先把第一个和最后一个元素交换（最大值和最小值交换）
- 然后将heap_size减1（从堆中去掉最大值）
- 然后经历一遍heapify的过程，继续保持大根堆、小根堆
- 大根堆和小根堆的堆顶，就是两个数组中的最大值和最小值
- 一直保持，较小的N/2个在大根堆中，较大的N/2个在小根堆中
- 这样就可以随时拿到中位数
代码实现
堆排序
时间复杂度O(N*logN)
额外空间复杂度O(1)
- 把数组通过heap_insert变成大根堆
- 把最后一个值和堆顶交换
- 把堆的大小减1 ==> 最大值保持不变的放在了最后一个位置，已经不在堆中了
- 再从剩下的堆中，做heapify的调整（堆顶被交换成了最小值），又变成了大根堆
- 再把当前堆中的最后一个值，和堆顶交换
- … …
class HeapSort:
def sort(self, arr: list):
"""启动堆排序"""
if arr is None or len(arr) < 2:
return
# 0~i 上形成大根堆
for i in range(len(arr)):
self.heap_insert(arr, i)
# 最后一个数和第一个数交换
heap_size = len(arr) - 1
arr[0], arr[heap_size] = arr[heap_size], arr[0]
# 直到大根堆的长度为0，所有的数就都有序了
while heap_size > 0:
self.heapify(arr, 0, heap_size)
arr[0], arr[heap_size - 1] = arr[heap_size - 1], arr[0]
# 进过上述操作之后，把heap_size - 1
heap_size -= 1
return arr
def heap_insert(self, arr: list, index: int):
"""在大根堆的基础上添加一个元素，heapInsert使其依然是大根堆"""
# 这个while是为了能 找到所有的父节点
while arr[index] > arr[int((index - 1) / 2)]:
# 只要我比我当前父节点的值大，我就和它完成交换
arr[index], arr[int((index - 1) / 2)] = arr[int((index - 1) / 2)], arr[index]
# 同时index向上走
# 当i走到0的时候，会出现arr[0] = arr[(0-1)/2], while也会停止
index = int((index - 1) / 2)
def heapify(self, arr: list, index: int, heap_size: int):
"""heap_size: 已经形成的堆的大小"""
# 当前元素的左节点
left = index * 2 + 1
# 这个while是为了能 找到所有的子节点
while left < heap_size:
# 找到左右节点中的 较大值(largest)
if left + 1 < heap_size and arr[left + 1] > arr[left]:
# 右节点也不越界，且 右节点>左节点
largest = left + 1
else:
largest = left
# 我和左右两个节点比较，如果还是我最大，就不用交换
largest = largest if arr[largest] > arr[index] else index
if largest == index:
break
arr[largest], arr[index] = arr[index], arr[largest]
index = largest
left = index * 2 + 1
list_ = [2, 4, 3, 6, 5, 8, 7, 10, 9]
arr = HeapSort().sort(list_)
print(arr)
评论区