二叉堆-对顶堆 P1090-P1168-P2085
二叉堆是一颗完全二叉树，而且每个根节点都比子节点大
封装好的大根堆模块有：（小根堆的话只需要将存入的权值添个负号，取出来的时候再负负得正）
python heapq模块 / deque中的PriorityQueue
C++ STL中priority_queue
python中的heapq主要操作：
heapq.heappush(堆名,元素) 插入元素
heapq.heappop(堆名) 返回最小元素（最大元素得在入堆和出堆时添负号）
heapq.heapify(列表名) 将列表->堆化（堆名等于原列表名）
初始化的话可以直接hp=[ ]
P1090
import heapqdef mc(n, fruits):#列表转堆heapq.heapify(fruits)total_cost = 0# 不断合并直到只剩下一堆while len(fruits) > 1:# 取出最小的两个元素first = heapq.heappop(fruits)second = heapq.heappop(fruits)cost = first + secondtotal_cost += cost# 将新元素放回堆中heapq.heappush(fruits, cost)return total_costn = int(input())
fruits = list(map(int, input().split()))print(mc(n, fruits))
P1168
那么就是一个大根堆和一个小根堆的对顶堆
1.如果新元素 ≤ 大顶堆的堆顶（即最大值），放进大顶堆。
2.否则放进小顶堆。
3.然后再检查是否平衡，不平衡就搬堆顶元素过去。
根据长度比较，保持两个堆的数目平衡（有点类似于双向bfs），从而方便提取中位数
import heapqclass DualHeap:def __init__(self):self.max_heap = [] # 大顶堆（用负数模拟）self.min_heap = [] # 小顶堆def add(self, num):if not self.max_heap or num <= -self.max_heap[0]:heapq.heappush(self.max_heap, -num)else:heapq.heappush(self.min_heap, num) if len(self.max_heap) > len(self.min_heap) + 1:heapq.heappush(self.min_heap, -heapq.heappop(self.max_heap))elif len(self.min_heap) > len(self.max_heap):heapq.heappush(self.max_heap, -heapq.heappop(self.min_heap))def get_median(self):if len(self.max_heap) > len(self.min_heap):return -self.max_heap[0] #其实这里一定是第一个分支#因为本题输出时个数为奇，一定是大顶堆多一个else:return (-self.max_heap[0] + self.min_heap[0]) / 2n=int(input())
l=list(map(int,input().split()))hq=DualHeap()
for i in range(n):hq.add(l[i])if (i+1)%2==1:print(hq.get_median())
P2085
P2085 最小函数值 - 洛谷
从小到大输出，数学关系上保证 F(x+1)>F(x)，但是在不同A,B,C的情况下无法比较F值，所以得用最小堆从小到大地平行地处理各个F
import heapqn,m=map(int,input().split())s=[]
for i in range(n):s.append(tuple(map(int,input().split())))#用tuple才方便下面解包hp=[]#直接用数组初始化即可
for i in range(len(s)):#从x等于1开始平行初始化a,b,c=s[i]fnow=a*1**2+b*1*1+cheapq.heappush(hp,(fnow,i,1))#元素：值，fi，xres=[]
for j in range(m):val,i,x=heapq.heappop(hp)res.append(val)a,b,c=s[i]newx=x+1fnow=a*newx**2+b*newx+cheapq.heappush(hp,(fnow,i,newx))print(*res)