我如何找到号码的线性时间使用堆位数？ [英] How do I find the median of numbers in linear time using heaps?

问题描述

维基百科说：

选择算法：寻找分钟，   最大，无论是最小值和最大值，中位数或   即使是第k个最大的元素可以是   线性使用时间堆完成。

Selection algorithms: Finding the min, max, both the min and max, median, or even the k-th largest element can be done in linear time using heaps.

所有它说的是，这是可以做到，而不是如何。

All it says is that it can be done, and not how.

您能否给我一些开始就如何可以用堆做？

Can you give me some start on how this can be done using heaps?

推荐答案

您将使用最小 - 最大，平均堆找到最小值，最大值和中位数都在固定时间（并采取线性时间来建立堆）。您可以使用顺序统计树，找到第k个最小/最大价值。在本文在最小 - 最大堆这两个数据结构的描述[PDF链接] 。最小 - 最大堆是二进制堆的最小堆和最大堆之间交替。

You would use a min-max-median heap to find the min, max and median in constant time (and take linear time to build the heap). You can use order-statistics trees to find the kth smallest/largest value. Both of these data structures are described in this paper on min-max heaps [pdf link]. Min-max heaps are binary heaps that alternate between min-heaps and max-heaps.

从纸：最小 - 最大，平均堆是一个二元堆具有以下属性：

From the paper: A min-max-median heap is a binary heap with the following properties:

1）的所有元素的中值位于根

1) The median of all elements is located at the root

2）的根的左子树是一个最小 - 最大的堆的大小天花板HL [（第（n-1）/ 2）]包含元素小于或等于的中位数。右子树是大小为地板一个最大最小堆小时[（第（n-1）/ 2）]仅含有元素大于或等于中值

2) The left subtree of the root is a min-max heap Hl of size ceiling[((n-1)/2)] containing elements less than or equal to the median. The right subtree is a max-min heap Hr of size floor[((n-1)/2)] containing only elements greater than or equal to the median.

文章接着解释了如何构建这样一个堆。

The paper goes on to explain how to build such a heap.

编辑：在更彻底地阅读报纸看起来好像建立最小 - 最大，平均堆，您需要先找到中位数（FTA：查找使用已知的线性时间的任何一个所有n个元素的中位数算法）。这就是说，一旦你已经建立了堆，您可以简单地通过保持在左侧和右侧的最大最小堆最小 - 最大堆之间的平衡维持的中位数。 DeleteMedian替换根目录或者最大最小堆分钟或最小 - 最大堆的最大值（两者保持平衡）。

Upon reading the paper more thoroughly it appears as though building the min-max-median heaps requires that you first find the median (FTA: "Find the median of all n elements using any one of the known linear-time algorithms"). That said, once you have built the heap you can maintain the median simply by maintaining the balance between the min-max heap on the left and the max-min heap on the right. DeleteMedian replaces the root with either the min of the max-min heap or the max of the min-max heap (whichever maintains the balance).

所以，如果你打算使用一个最小 - 最大，平均堆找到一个固定的数据位数设置你SOL但如果你是在一个不断变化的数据通过其设置是可能的。

So if you plan on using a min-max-median heap to find the median of a fixed data set you're SOL but if you are using it on a changing data set it is possible.

这篇关于我如何找到号码的线性时间使用堆位数？的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！