Laz*_*zer 50 algorithm heap time-complexity median
维基百科说:
选择算法:使用堆可以在线性时间内完成最小值,最大值,最小值和最大值,中值或甚至第k个最大元素的查找.
它说的只是它可以完成,而不是如何完成.
你能给我一些关于如何使用堆来完成这项工作的开始吗？
Nik*_*chi 21
您将使用min-max-median堆来查找恒定时间内的最小值,最大值和中值(并使用线性时间来构建堆).您可以使用order-statistics树来查找第k个最小/最大值.本文中关于min-max堆[pdf link]描述了这两种数据结构.最小 - 最大堆是在最小堆和最大堆之间交替的二进制堆.
从论文:min-max-median堆是具有以下属性的二进制堆:
1)所有元素的中位数位于根
2)根的左子树是尺寸上限[((n-1)/ 2)]的最小 - 最大堆H1,其包含小于或等于中值的元素.右子树是大小为[((n-1)/ 2)]的最大最小堆Hr,仅包含大于或等于中值的元素.
本文接着解释如何构建这样的堆.
编辑:在更彻底地阅读论文时,似乎构建最小 - 最大 - 中值堆需要您首先找到中位数(FTA:"使用任何一种已知的线性时间算法查找所有n个元素的中值") .也就是说,一旦构建了堆,就可以通过维持左边的最小 - 最大堆和右边的最大最小堆之间的平衡来维持中值.DeleteMedian用最大最小堆的最小值或最小最大堆的最大值(以保持平衡为准)替换root.
因此,如果您计划使用最小 - 最大 - 中值堆来查找固定数据集的中位数,那么您就是SOL,但如果您在更改的数据集上使用它,则可能.