c++ - 对数组进行部分排序

Question

部分排序可以使用 std::partial_sort 完成。

部分分拣手段

5 7 4 2 8 6 1 9 0 3

对 3 个元素进行部分排序后

0 1 2 7 8 6 5 9 4 3

http://en.cppreference.com/w/cpp/algorithm/partial_sort。

但是，当某些元素已经排序时，这并不是最好的。

是否还有其他此类功能可以这样做并利用部分排序的数组。

Answer 1

您可以使用流式中位数算法的改编版本来跟踪k一组术语中的最小术语。您可以使用std::priority_queue最小和最大堆。

该算法将像这样工作：

• 最大堆用于保存k最小项
• 最小堆用于保存所有其他项
• 对于要跟踪的每个术语，决定应将其添加到哪个堆，并将其添加到那里
  • 如果最大堆的大小小于k将其添加到那里，否则
  • 如果项小于最大堆的顶部，则将其添加到那里，否则
  • 将术语添加到最小堆
• 如果最大堆的顶部有多个k术语，则弹出顶部的术语，并将其推入最小堆

如果您需要对术语进行排序，您可以按降序将它们从最大堆中弹出，以相反的顺序将它们放在一个数组中，从而为您留下一个排序后的数组。如果将容器传递给最大堆的构造函数，则可以复制容器并对其进行排序。

默认情况下std::priority_queue是最大堆。要使其成为最小堆，您需要修改一些模板参数。

typedef std::priority_queue<int> MaxHeap;
typedef std::priority_queue
    <
        int,
        std::priority_queue<int>::container_type,
        std::greater<int>
    > MinHeap;