对数组进行部分排序

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：:p riority_queue 作为最小堆和最大堆。

算法是这样工作的:

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

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

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

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