SplMaxHeap, куча
Решение (копипаст)
class Solution {
function maxKelements($a, $k) {
$pq = new SplMaxHeap();
$res = 0;
foreach ($a as $x) $pq->insert($x);
while ($k--) {
$cur = $pq->extract();
$res += $cur;
$pq->insert(ceil($cur / 3));
}
return $res;
}
}
Реализация задач через кучу (Heap) — это классический подход в алгоритмических решениях, который особенно полезен для работы с задачами, требующими эффективного поиска минимальных или максимальных элементов, обработки динамически изменяющихся данных и других задач, где важен приоритет.
Примеры:
1. Алгоритм Дейкстры для поиска кратчайшего пути
Алгоритм Дейкстры используется для нахождения кратчайшего пути в графе с положительными весами ребер. Основное действие — это нахождение наименьшего пути среди еще не посещенных вершин.
- В этом случае, очередь с приоритетом на основе кучи позволяет эффективно извлекать вершину с минимальным расстоянием на каждом шаге, что ускоряет работу алгоритма.
- Время работы алгоритма существенно снижается, если использовать кучу вместо линейного поиска минимального элемента, давая сложность (O((V + E) \log V)), где (V) — количество вершин, а (E) — количество ребер.
2. Сортировка слиянием (k) отсортированных списков
Задача заключается в том, чтобы объединить несколько отсортированных списков в один отсортированный. Например, при обработке данных с нескольких источников или потоков данных.
- Куча может быть использована для выбора минимального элемента из всех списков. В каждый момент мы извлекаем минимальный элемент из кучи и добавляем следующий элемент из того списка, откуда был извлечен предыдущий.
- Это решение работает за (O(n \log k)), где (n) — общее количество элементов, а (k) — количество списков. Без кучи это потребовало бы полного слияния за время (O(nk)).
3. Поиск медианы в потоке данных
Эта задача заключается в том, чтобы находить медиану в массиве, который постоянно увеличивается новыми элементами (поток данных).
- Здесь используется комбинация двух куч: max-куча для хранения меньшей половины данных и min-куча для хранения большей половины. Медианой будет либо максимальный элемент из max-кучи, либо среднее между максимальным элементом max-кучи и минимальным элементом min-кучи, в зависимости от количества элементов.
- Обновление медианы можно выполнить за (O(\log n)) при каждом добавлении нового элемента.
4. Задача о (k)-м максимальном/минимальном элементе
Иногда необходимо найти (k)-й по величине элемент в неотсортированном массиве. Например, когда нужно выбрать несколько лучших кандидатов или наибольшие значения из множества.
- Куча с ограничением размера (k) позволяет решить задачу за (O(n \log k)). Мы добавляем элементы в кучу и поддерживаем её размер (k), а затем просто извлекаем максимальный или минимальный элемент. В отличие от сортировки массива, это решение гораздо эффективнее для больших данных.
5. Алгоритм Хаффмана для кодирования данных
Алгоритм Хаффмана используется для создания эффективных (по размеру) кодов для символов, основываясь на их частотах появления.
- В этом алгоритме минимальная куча используется для того, чтобы эффективно находить два символа с наименьшими частотами на каждом шаге объединения. Это позволяет построить оптимальное бинарное дерево.
- Куча позволяет построить кодовое дерево за время (O(n \log n)), где (n) — количество различных символов.
6. Задачи диспетчеризации задач и очереди с приоритетом
В реальных системах, таких как операционные системы или облачные сервисы, очереди задач часто требуют обработки с приоритетом (например, планирование задач в процессоре или управление задачами на сервере).
- Очередь с приоритетом на основе кучи позволяет быстро добавлять задачи и выбирать задачи с наивысшим приоритетом для выполнения. Это особенно важно в реальном времени, когда задачи приходят асинхронно и приоритеты могут изменяться.
7. Обработка логов и события с окнами по времени
Задачи, связанные с анализом логов или обработкой событий с временными метками, также могут эффективно решаться через кучи. Например, когда необходимо хранить ограниченное количество последних событий или находить самые "свежие" события по времени.
- Мини-куча может быть использована для поддержания (k) самых свежих событий, автоматически удаляя старые и добавляя новые по мере их поступления. Это позволяет обрабатывать данные за (O(\log k)) на каждое событие.
8. Потоковые вычисления и большие данные
В задачах анализа больших данных, когда данные поступают непрерывным потоком, куча также используется для эффективной работы с динамически меняющимися данными. Например, нахождение топ-элементов в потоке данных или в больших базах данных (например, Google использует подобные алгоритмы для поиска наиболее релевантных страниц).
- Куча позволяет поддерживать динамический список топ-значений, извлекать важные данные и выполнять вычисления на ходу с минимальными затратами памяти и времени.
9. Виртуальные машины и управление памятью
Виртуальные машины и интерпретаторы используют кучи для управления памятью (heap memory), где хранятся объекты с динамическим временем жизни. Это отдельный тип использования кучи, где важно эффективное управление памятью, сборка мусора и перераспределение ресурсов.