Будет ли быстрее использовать двоичную кучу, чтобы получить максимальное количество целых чисел из массива, или использовать быструю сортировку
Чтобы получить наибольшее количество целых чисел X из массива, думаете ли вы, что использование двоичной кучи будет быстрее:
- двоичная куча, чтобы получить наибольшее целое число
- хранить наибольшее целое число
- удалить наибольшее целое число из массива
- повторять, пока мы не получим наибольшее количество X из массива
Или было бы быстрее просто использовать быструю сортировку и взять максимальное количество х целых чисел из массива?
РЕДАКТИРОВАТЬ: Я должен также добавить, что массив не может оставаться отсортированным, поскольку он имеет несколько переменных, по которым мы хотим отсортировать, например:
class cl{
int var;
int var1;
int var2;
};
cl clArr[];
Таким образом, мы можем запросить, чтобы получить самые высокие целые числа от любой из переменных.
Записывая это, кажется, что быстрая сортировка может быть лучшей идеей, хотя я хотел бы получить некоторые мнения, пожалуйста, в основном то, что будет самым быстрым вариантом.
Спасибо
Решение
Вам нужно внедрить оба этих решения и выполнить профилирование с реальными данными, чтобы выяснить, какие из них быстрее.
Другие решения
Давайте рассмотрим пример для обоих этих случаев:
Метод 1 (использовать Max Heap): —
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)