Куча K крупнейших элементов: методы поиска K крупнейших элементов из заданного набора

  1. Максимальная куча:

    • Создать максимальную кучу из заданных элементов.
    • Извлеките k самых больших элементов, многократно извлекая максимальный элемент k раз.
  2. Минимальная куча:

    • Создайте минимальную кучу размером k из первых k элементов.
    • Для каждого оставшегося элемента сравните его с корнем минимальной кучи.
    • Если элемент больше, замените корень элементом и создайте минимальную кучу.
    • В конце минимальная куча будет содержать k самых больших элементов.
  3. Сортировка:

    • Отсортируйте заданные элементы по убыванию.
    • Извлечь первые k элементов из отсортированного списка.
  4. Алгоритм быстрого выбора:

    • Используйте алгоритм быстрого выбора, чтобы найти k-й по величине элемент.
    • Разбейте элементы вокруг опорной точки, пока опорная точка не достигнет индекса k.
    • Все элементы справа от опорной точки будут больше опорной точки.
    • Извлечь k крупнейших элементов из сводного индекса в конец списка.
  5. Приоритетная очередь:

    • Используйте приоритетную очередь для хранения элементов.
    • Вставить все элементы в очередь приоритетов.
    • Извлечь k самых больших элементов из приоритетной очереди.