二叉堆笔记

编程入门行业动态更新时间:2024-10-03 21:24:45

二叉堆<a href=https://www.elefans.com/category/jswz/34/1770047.html style= 笔记"/>

二叉堆：维护数组中数据优先级的完全二叉树，每个子树皆满足该性质。

小根堆和大根堆分别对应堆顶数据优先级最小和优先级最大（也可以是数据的最小值和最大值），堆顶对应树结构的根。对处理优先级问题，二叉堆为首选。

二叉堆一般用STL中优先队列priority_queue实现。

1、两个二叉堆维护

P1168 中位数 - 洛谷 | 计算机科学教育新生态 (luogu)

中位数，可以用一个大根堆来维护中位数前的数，用小根堆来维护中位数后的数，两个堆内个数相同。

当两个根堆中个数不同时，就要把个数多的堆里的数向个数少的堆里的数分配，直至两个堆内元素重新一致。

2、全局最优先

P2085 最小函数值 - 洛谷 | 计算机科学教育新生态 (luogu)

将每个函数较小值统统压进小根堆中，小根堆依次输出全局最小的几个值。

更多推荐

二叉堆笔记

本文发布于:2024-02-28 14:56:19，感谢您对本站的认可！

笔记二叉堆

评论列表（有 0 条评论）