c - Top N 记录排序以仅返回排序数组中特定范围内的数字

Question

我有一个哈希表，可能包含大约 1-5 百万条记录。我需要遍历它以选择其中的一些条目，然后按某种顺序对它们进行排序。另外，我实际上并不需要所有排序的元素，而是说一些落在特定范围内的元素。例如。如果哈希表包含 100 万条记录，我可能只需要前 1000-2000 条记录。有没有标准的排序算法？如果不是，我可以实现 2 遍算法，首先通过查找第 1000 条记录，然后说下一遍以确定接下来的 1000 条记录可能是什么。是否有任何可用的堆排序实现？我猜 topN 堆排序的任何实现都会对此有所帮助。我可以使用的数组大小也有限制。如果我的数组大小仅为请求的记录数，那将是最好的。

Answer 1

对此有一个标准算法。正如@Ivaylo Strandjev 在他的回答中指出的那样，快速选择是完成此操作的典型方式。但是，在这种情况下，这将需要 O(n) 额外空间，因为您无法重新排列哈希表。

另一种常用的方式是堆。如果你想要第 1000 到第 2000 个最小的项目，你可以分两次完成。首先，您使用堆找到第 1000 个最小的项目。然后，您执行另一遍以获取 1000 个大于或等于您在第一遍中找到的最小项。像这样的东西:

第一关:

h = new max heap
add first 1000 items to heap
for i = 1000 to n-1
    if hashtable[i] < heap.peek()
        heap.remove_first()
        heap.add(item)

第 1000 个最小的项目现在是堆中最大的项目。所以:

smallest = heap.remove_first()

现在创建一个大小为 1,000 的新堆并添加该项目。然后再次遍历列表，只添加 >= 最小的项目:

h = new max heap
for i = 0 to n-1
    if hashtable[i] >= smallest
        if heap.count < 1000
            heap.add(item)
        else if hashtable[i] < heap.peek()
            heap.remove_first()
            heap.add(item)

完成后，堆中将包含项目 1000 到 2000。

这项技术的一个好处是您可以分配单个数组并像处理堆一样操作它。参见 Binary heap了解概览，或查看我的 series on heaps .前三篇文章解释了问题并提供了足够的信息，您应该能够在 C 中实现一个简单的堆。您可以使用 C# 中的代码示例作为起点。

不过请记住，我在上面的示例中使用了最大堆。我的博文中的讨论是关于最小堆的，因此您必须确保相应地更改比较。

堆选择的复杂度为 O(n log k)，其中 n 是列表的大小，k 是要选择的项目数。如果您希望在将项目返回数组时对其进行排序，则必须对堆进行排序(或逐一删除项目)。无论哪种情况，都是 O(k log k)。因此，您的总运行时间将与 (n log k) + (k log k) 成正比。

虽然快速选择渐近地比堆选择快，但实际上当您选择 1% 或更少的项目时，堆选择通常比快速选择快。因此，如果您从一百万个列表中选择 1,000 个项目，堆选择几乎肯定会更快。参见 When theory meets practice了解详情。

更新

正如 OP 在评论中指出的那样，这可能需要相当大的堆。例如，如果要查找第 10,000 到第 11,000 个项目，则第一遍需要大小为 10,000 的堆。第二遍仍然只需要 1,000 个项目的堆。使用朴素的方法，选择第 990,000 到第 999,000 个项目将需要大小为 998,000 的堆。然而，你可以反过来:使用最小堆，然后你只需要一个大小为 1,000 的堆(即找到第 1,000 到第 2,000 个最大的项目)。因此，第一次传递所需的堆大小为 min(r1, (n-r2))。第二遍所需的堆大小为 r2 - r1。

您可以通过创建一个大小为 r2 的堆来实现。执行一次传递以获得最小的 r2 项目，然后从中选择顶部的 r2-r1 项目。它使复杂度 (n log r2) + (k log r2)。 k 等于 r2-r1。同样，如果 r1 > n/2，您可以使用最小堆来减少内存需求。

我考虑过使用 Min-max 堆在单次传递中执行此操作的可能性，但我认为它行不通。