Heaps

Почему вас это должно волновать? Представьте, что у вас есть тысячи задач, каждая из которых имеет разный приоритет, и вам всегда нужно сначала обработать задачу с наивысшим приоритетом. Перебирать все задачи каждый раз было бы дорого. Куча обеспечивает эффективный способ многократного доступа к самому маленькому или самому большому элементу, при этом позволяя добавлять и удалять новые элементы. Кучи особенно полезны для: Приоритетные очереди Планирование ЦП и задач Нахождение наименьшего или наибольшего значения Алгоритм Дейкстры кратчайшего пути Алгоритм минимального связующего дерева Прима Сортировка кучей Стриминг и проблемы топ-К Кучи также важны, поскольку они показывают, как можно эффективно представить дерево с помощью массива. Проблема Предположим, система получает следующие задачи: Задача А → Приоритет 5 Задача Б → Приоритет 2 Задача C → Приоритет 8 Задача D → Приоритет 1 Система должна сначала обработать самую важную задачу. Если мы просто сохраним их в массиве: [5, 2, 8, 1] нам нужно будет выполнить поиск по коллекции, чтобы найти наивысший приоритет. Мы могли бы отсортировать всю коллекцию, но это потребует ненужной работы, когда задачи постоянно добавляются и удаляются. Нам нужна структура, которая эффективно поддерживает: