堆的概念
● 堆：一种特殊的完全二叉树结构
????????? 大根堆：一棵完全二叉树，满足任一节点都比其孩子节点大
????????? 小根堆：一棵完全二叉树，满足任一节点都比其孩子节点小
堆的性质
堆的性质——向下调整：
????????? 假设根节点的左右孩子树都是堆，但根节点不满足堆的性质
????????? 可以通过一次向下的调整来将其变成一个堆
堆排序过程——农村包围城市的策略
?????????（1）建堆
?????????（2）得到堆顶元素，为最大元素
?????????（3）去掉堆顶，将堆最后一个元素放到堆顶，此时可通过一次调整重新使堆有序
?????????（4）堆顶元素为第二大元素
?????????（5）重复步骤3，直到堆变空
?????代码实现
def adjust(li, low, hight):
"""
:param li: 列表
:param low: 堆的根节点位置
:param hight: 堆的最后一个元素的位置
:return:
"""
i = low # i最开始指向根节点
j = 2*i + 1 # j开始是左孩子
tmp = li[low] # 把堆顶存起来
while j <= hight:
if j+1 <= hight and li[j+1] > li[j]:
j += 1 # j指向右孩子
if li[j] > tmp:
li[i] = li[j]
i = j # 往下一层看
j = 2*i + 1
else: # tmp更大，把tmp放到i的位置上
li[i] = tmp # 把tmp放到某一级领导位置上
break
else:
li[i] = tmp # 把tmp放到叶子结点上
def heapSort(li):
# 构造堆，农村包围城市
n = len(li)
for i in range((n-2)//2, -1, -1):
# i表示建堆的时候调整的部分的根的下标
adjust(li, i, n-1)
# 建堆完成
# print(li)
# 挨个输出
for i in range(n-1, -1, -1):
# i指向当前堆的最后一个元素
li[0], li[i] = li[i], li[0]
adjust(li, 0, i-1) # i-1是新的high
li = [i for i in range(10)]
import random
random.shuffle(li)
print(li)
heapSort(li)
print(li)
?堆排序——内置模块
● python内置模块——heapq
● 常用函数
????????? heappush(heap,item)
????????? heapify(heap)?
????????? heappop(heap)
注：内置模块实现的是小根堆用，假如要实现大根堆，得用小根堆来构造大根堆
（1）heappush(heap,item)
heapq.heappush()是往堆中添加新值，此时自动建立了小根堆
????????◆ 建立小根堆
import heapq
nums = [] #创建一个空堆
heapq.heappush(nums, 5)
heapq.heappush(nums, 2)
heapq.heappush(nums, 0)
heapq.heappush(nums, 3)
heapq.heappush(nums, 8)
heapq.heappush(nums, 6)
heapq.heappush(nums, 1)
heapq.heappush(nums, 9)
heapq.heappush(nums, 4)
heapq.heappush(nums, 7)
print(nums) # [0, 3, 1, 4, 7, 6, 2, 9, 5, 8]????????◆ 建立大根堆
????????heapq里面没有直接提供建立大根堆的方法，可以采取如下方法：
? ? ? ? （1）每次push时给元素加一个负号（即取相反数），此时最小值变最大值，反之亦然；
????????（2）那么实际上的最大值就可以处于堆顶了，返回时再取负即可。
????????或者
????????（1）先建立小根堆，然后每次heappop()，此时得到从小大的排列，再reverse?
????????（2）利用相反数建立大根堆，然后heappop(-元素)。即push(-元素)，pop(-元素)
# 建立大根堆
nums = [0, 3, 1, 4, 7, 6, 2, 9, 5, 8]
heap = []
for num in nums:
heapq.heappush(heap, -num)
# 返回时再取负即可
print(list(map(lambda x: -x, heap))) # [9, 8, 6, 5, 7, 1, 2, 0, 4, 3]（2）heapify(heap)
?????????heapq.heapfy()是以线性时间将一个列表转化为小根堆
????????◆ 建立小根堆
import heapq
import random
nums = list(range(10))
random.shuffle(nums)
print(nums) # [5, 2, 0, 3, 8, 6, 1, 9, 4, 7]
# heapq.heapfy()是以线性时间将一个列表转化为小根堆
heapq.heapify(nums)
print(nums) #[0, 2, 1, 3, 7, 6, 5, 9, 4, 8]?????????◆ 建立大根堆
# 建立大根堆
nums = [2, 1, 3, 7, 6, 5, 9, 4, 8]
heap = list(map(lambda x: -x, nums))
heapq.heapify(heap)
print([-x for x in heap]) # [9, 8, 5, 7, 6, 2, 3, 4, 1]?（3）heappop(heap)
????????heapq.heappop()是从堆中弹出并返回最小的值
import heapq
import random
nums = list(range(10))
random.shuffle(nums)
print(nums) # [5, 2, 0, 3, 8, 6, 1, 9, 4, 7]
# heapq.heapfy()是以线性时间将一个列表转化为小根堆
heapq.heapify(nums)
print(nums) #[0, 2, 1, 3, 7, 6, 5, 9, 4, 8]
# 挨个输出
n = len(nums)
for i in range(n):
# heappop每次删除并返回列表中最小的值
print(heapq.heappop(nums), end=' ')参考：Python中heapq模块浅析_chandelierds的博客-CSDN博客_heapq python
top K问题
?代码实现
import heapq
import random
def adjust(li, low, hight):
i = low # i最开始指向根节点
j = 2*i + 1 # j开始是左孩子
tmp = li[low] # 把堆顶存起来
while j <= hight:
if j+1 <= hight and li[j+1] < li[j]:
j += 1 # j指向右孩子
if li[j] < tmp:
li[i] = li[j]
i = j # 往下一层看
j = 2*i + 1
else: # tmp更大，把tmp放到i的位置上
li[i] = tmp # 把tmp放到某一级领导位置上
break
else:
li[i] = tmp # 把tmp放到叶子结点上
def topk(nums, k):
heap = nums[:k]
# 1.建堆
for i in range((k-2)//2, -1, -1):
adjust(heap, i, k-1)
# 2. 遍历
for i in range(k, len(nums)-1):
if nums[i] > heap[0]:
heap[0] = nums[i]
adjust(heap, 0, k-1)
# 3.挨个输出前k个数
for i in range(k-1, -1, -1):
heap[0], heap[i] = heap[i], heap[0]
adjust(heap, 0, k-1)
return heap
nums = list(range(10))
print(nums) # [0, 1, 2, 3, 4, 5, 6, 7, 8, 9]
random.shuffle(nums)
print(topk(nums, 5)) # [5, 6, 8, 7, 9]?