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

Question

要从数组中获取最多 X 数量的整数，你们认为使用像这样的二叉堆会更快吗:

• 二叉堆取最大整数
• 存储最高整数
• 从数组中取出最大的整数
• 重复，直到我们从数组中获得最高的 X 数量

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

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

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

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

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

谢谢

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)

方法二(使用快速排序):-

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)