c++ - 使用二进制堆从数组中获取前 x 个整数或使用快速排序会更快吗

Question

要从数组中获取最大 X 数量的整数，你们是否认为使用像这样的二进制堆会更快：

或者只使用快速排序并从数组中获取前 x 个整数会更快吗？

编辑：我还应该补充一点，数组不能保持排序，因为它有几个我们想要排序的变量，例如：

class cl{
   int var;
   int var1;
   int var2;
};
cl clArr[];

因此，我们可以请求从任何变量中获取最大整数。

写下来，似乎快速排序可能是一个更好的主意，尽管我想请一些意见，主要是最快的选择。

谢谢

score 0 · Accepted Answer

让我们为这两种情况举一个例子：-

方法1（使用最大堆）：-

1) Build a Max Heap tree in O(n)
2) Use Extract Max k times to get k maximum elements from the Max Heap O(klogn)

Time complexity: O(n + klogn)

方法2（使用快速排序）：-

1) Sort the elements in descending order in O(nLogn)
2) Print the first k numbers of the sorted array O(k).

Time complexity: O(nlogn)

score 0 · Accepted Answer

您需要实现这两种解决方案，并使用真实数据进行一些分析，以找出哪个更快。

2 回答 2