维基百科 http://en.wikipedia.org/wiki/Heap_(data_structure)#Heap_applications says:
选择算法：找到最小值，
最大值，最小值和最大值，median， 或者
甚至第 k 大元素也可以是
使用堆在线性时间内完成。
它只说可以做到，而不是如何做到。
您能给我一些关于如何使用堆来完成此操作的开始吗？
您可以使用最小-最大-中值堆在恒定时间内查找最小值、最大值和中值（并花费线性时间来构建堆）。您可以使用顺序统计树来查找第 k 个最小/最大值。这两种数据结构都在这篇关于最小-最大堆的论文 [PDF] http://cg.scs.carleton.ca/%7Emorin/teaching/5408/refs/minmax.pdf。最小-最大堆是在最小堆和最大堆之间交替的二元堆。
来自论文：
最小-最大-中值堆是具有以下属性的二叉树：
-
所有元素的中位数位于根
-
根的左子树是大小为上限[((n-1)/2)]的最小-最大堆Hl，包含小于或等于中位数的元素。右子树是大小为 Floor[((n-1)/2)] 的最大最小堆 Hr，仅包含大于或等于中位数的元素。
论文接着解释了如何构建这样的堆。
更彻底地阅读本文后，似乎构建最小-最大-中值堆需要您首先找到中位数（FTA：“使用任何一种已知的线性时间算法查找所有 n 个元素的中值”）。也就是说，一旦构建了堆，您只需保持左侧的最小-最大堆和右侧的最大-最小堆之间的平衡即可维持中位数。 DeleteMedian 将根替换为最大-最小堆的最小值或最小-最大堆的最大值（以保持平衡的为准）。
因此，如果您计划使用最小-最大-中值堆来查找固定数据集的中值，那么您就可以了，但是如果您在变化的数据集上使用它，则这是可能的。
本文内容由网友自发贡献，版权归原作者所有，本站不承担相应法律责任。如您发现有涉嫌抄袭侵权的内容，请联系:hwhale#tublm.com(使用前将#替换为@)
