如何在线性时间内使用堆find数字的中位数？
维基百科说：
selectalgorithm：find最小值，最大值，最小值和最大值， 中值 ，甚至第k个最大元素都可以使用堆在线性时间内完成。
它所说的是，它可以做到，而不是如何。
你可以给我一些开始如何使用堆可以做到这一点？
您将使用最小最大中值堆来查找恒定时间内的最小值，最大值和中值（以线性时间构build堆）。 您可以使用订单统计树来查找第k个最小/最大值。 这两种数据结构都在本文中描述最小最大堆[pdf链接] 。 Min-max堆是在最小堆和最大堆之间交替的二进制堆。
从论文中可以看出：min-max-median heap是一个具有以下属性的二进制堆：
1）所有元素的中位数位于根
2）根的左子树是大小为ceiling [（（n-1）/ 2）]的最小 – 最大堆H1，其中包含小于或等于中值的元素。 右子树是仅包含大于或等于中值的元素的大小为[（（n-1）/ 2）]的最大 – 最小堆Hr。
本文继续解释如何build立这样一个堆。
编辑：在更彻底地阅读文章时，似乎build立最小最大中值堆要求您首先find中位数（FTA：“使用任何一个已知的线性时间algorithm找出所有n个元素的中位数”） 。 也就是说，一旦build立了堆，只需维持左边最小最大堆积和右边最大最小堆积之间的平衡，就可以维持中位数。 DeleteMedian用最大 – 最小堆的最小值或最小 – 最大堆的最大值（保持平衡的那一个）replace根。
所以，如果您打算使用最小最大中值堆来查找固定数据集的中位数，那么您就是SOL，但是如果您正在使用一个不断变化的数据集，那么这是可能的。
请参阅selectalgorithm的维基百科页面。 具体来看，BFPRTalgorithm和Mediansalgorithm中值。 BFPRT是概率线性的，并以快速sorting为模型; Medians的中位数保证是线性的，但是有一个很大的常数因子，所以在实践中可能需要更长的时间，这取决于数据集的大小。
如果你只有几百或几千个元素来select中位数，我怀疑一个简单的快速sorting和直接索引是最简单的。
有可能有更好的algorithm，但这是我该怎么做：
有两个桶和一个值。 价值是中位数，两个桶比“中位数大”和“小于中位数”。 对于数组中的每个元素x ，重新平衡桶，使得big_bucket和small_bucket相差不超过1。 当把物品从大桶移到小桶时，他们首先必须通过中间值才能到达那里（也就是说，相差2将成功地从一个桶推到下一个桶 – 相差1将推动一个元素从一个桶到中间值）。在你第一次通过数组时，值应该是你的中位数。
当原始问题被问到时，可能还没有，但是现在维基已经链接到源代码，这里是： http : //ftp.cs.purdue.edu/research/technical_reports/1991/TR%2091-027。 PDF格式
具体来说，转到第17页，看看RSEL4的描述。 他们在定理3.2中certificate了这个第k个selectalgorithm的时间复杂度是O（k）。 所以它需要你O（n）来build立堆，和一个额外的O（k）来find第k个最小的项目。
它并不像其他一些答案所build议的那样直截了当
如果你对堆数据结构有更多的了解，那么你会很容易理解，实际上是这样的。 堆结构可以在O（n）时间内build立，有最小堆和最大堆。 min堆根元素会给你最小的元素。 最大堆根元素将给你最大的元素。 只要build立堆，你可以find最小和最大。 对于中位数和第k位最大的同样的想法，在构build堆的同时，可以通过查看树的左侧或右侧分支并保持恒定的内存量来存储元素号，从而find中值和第k个最大值。 等等
将第一个整数存储在数组中，并将计数器设置为1.然后遍历向量中剩余的整数。 如果数组中的当前整数与存储的整数相同，则计数器加1，否则计数器减1。 如果计数器达到零，则丢弃存储的整数并将其replace为数组中的当前整数。 当你终于结束所有整数时，你只剩下一个候选人。 然后，您需要再次遍历数组，并计算候选人的出现次数，以validation这是否是一个统治者。
static int FindDominator(int[] arr) { int counter = 1; int candidate = arr[0]; for(int i = 1; i < n; i++) { if(arr[i] == candidate) counter++ else { counter--; if(counter == 0) { candidate = arr[i]; counter = 1; } } } counter = 0; for(int i = 0; i < n; i++) { if(arr[i] == candidate) counter++; } if(counter > n / 2) return candidate; else return -1; }
很明显，O（n）中的min和max很容易，不需要堆。
到目前为止，通过维持k个最大k值的堆，可以简单地完成第k个最大值。 运行时间将是O（n * logk）。 如果k是固定大小且k << n，则可以调用线性时间。
我不认为中位数是可能的。 只需创build一个O（n）大小的堆，就需要O（n * logn）时间。
编辑：好吧，想一想这个多一点，IVlad是正确的。 您可以在O（n）中创build一个固定大小的堆。 但是…这对他的中位数问题没有帮助。 线性堆创build技术只会产生一个有效的堆作为最终的输出。 执行n次插入的简单方法是，在每个步骤之后导致有效的堆是O（n * logn）。
在我看来，使用堆寻找中位数将需要使用那些运行子堆。 例如，在这里发布了一个答案（似乎现在已经被删除），链接到一个博客文章，提出了这个问题的algorithm。 它使用两个堆（更小的一半和更大的一半）跟踪运行中位数，因为它只是单次传递数据。 这将需要更慢，天真的堆方法，因为它取决于维护有效的堆，因为它插入和从中删除。
有没有其他的方法来find使用线性一次性堆创build技术的中位数？
