Рубрики

Структуры данных | Разное | Вопрос 3

Какая структура данных наиболее эффективна для поиска 10 самых больших элементов из 1 миллиона элементов, хранящихся в файле?
(A) Мин куча
(B) Макс кучи
(С) BST
(D) отсортированный массив

Ответ: (А)
Объяснение: Минимальной кучи размера 10 достаточно, чтобы найти 10 самых больших предметов. Алгоритм может быть задан следующим образом:
1. Создайте минимальную кучу с первыми 10 элементами.
2. Для каждого оставшегося элемента, проверьте, если
2.1. Предмет больше, чем предмет, хранящийся в голове кучи мин.
2.1.1 Если да, замените его новым элементом. Баланс мин кучи.
2.1.2 Если нет, ничего не делать.

Наконец, минимальная куча будет содержать 10 самых больших предметов.

Рекомендуемые посты:

Структуры данных | Разное | Вопрос 3

0.00 (0%) 0 votes