algorithm - 如何使用堆在线性时间内找到数字的中位数？

Question

Wikipedia说:

Selection algorithms: Finding the min,max, both the min and max, median, oreven the k-th largest element can bedone in linear time using heaps.

它只是说它可以完成，而不是如何完成。

你能告诉我如何使用堆来完成这个吗？

Answer 1

您将使用最小-最大-中值堆在恒定时间内找到最小值、最大值和中值(并用线性时间来构建堆)。您可以使用顺序统计树来查找第 k 个最小/最大值。 this paper on min-max heaps [PDF] 中描述了这两种数据结构。 .最小-最大堆是在最小堆和最大堆之间交替的二叉堆。

来自论文:

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

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

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.

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

在更彻底地阅读这篇论文后，似乎构建最小-最大-中值堆需要您首先找到中值(FTA:“使用以下任一方法找到所有 n 个元素的中值已知的线性时间算法”)。也就是说，一旦构建了堆，就可以通过保持左侧的最小-最大堆和右侧的最大-最小堆之间的平衡来保持中位数。 DeleteMedian 用最大-最小堆的最小值或最小-最大堆的最大值(以保持平衡为准)替换根。

因此，如果您计划使用最小-最大-中值堆来查找固定数据集的中值，那么您就是 SOL，但如果您在不断变化的数据集上使用它，则有可能。