算法合集之《左偏树的特点及其应用》.ppt

左偏树的特点及其应用左偏树的定义左偏树的定义——左偏性质左偏树的性质左偏树的操作左偏树的操作——合并左偏树的操作——合并左偏树的操作——合并左偏树的操作——合并左偏树的操作——合并左偏树的操作——合并左偏树的操作——合并左偏树的操作——合并左偏树的操作——合并左偏树的操作——合并左偏树的操作——合并左偏树的操作——合并左偏树的操作——合并左偏树的操作——插入左偏树的操作——删除例题：数字序列假设数列a1,a2,…,ak的最优解为b1,b2,…,bk
合并{bi}中相同的项，得到m个区间和数列s1,s2,…,sm
显然，si为数列a中，下标在第i个区间内的各项的中位数。若ak+1>sm，直接令sm+1＝ak+1，得到前k+1项的最优解；
否则，将ak+1并入第m个区间，并更新sm
不断检查最后两个区间的解sm-1和sm，若sm-1≥sm，合并最后两个区间，并令新区间的解为该区间内的中位数。下面考虑数据结构的选取
我们需要维护若干个有序集，并能够高效完成下面两个操作：
合并两个有序集
查询某个有序集的中位数
进一步分析，加入一个元素后，发生一连串合并操作，合并后有序集的中位数不会比原来大
因此，每个有序集内只保存较小的一半元素，查询中位数操作转化为取最大元素操作。例题：数字序列——算法分析例题：数字序列——算法分析总结谢谢大家