Структуры Данных: Куча

"Куча - это линейная структура данных, которая организует элементы в порядке приоритета, с самым большим элементом всегда в начале. Представленная как полное бинарное дерево, куча гарантирует, что каждый родительский узел имеет более высокий приоритет, чем его дети. Операции, такие как выбор, вставка и удаление, имеют сложность O(log n), поскольку они включают в себя подъем или спуск по дереву для поддержания порядка. Изменение приоритета также имеет сложность O(log n). Алгоритм "подъем" перемещает элементы вверх по дереву, если их приоритет выше, чем у родителей. Алгоритм "спуск" перемещает элементы вниз, если их приоритет ниже, чем у детей. Вставка включает добавление нового элемента в конец и подъем его по дереву для поддержания порядка. Удаление элемента с наивысшим приоритетом включает замену его последним элементом и спуск этого элемента для поддержания порядка. Куча может быть построена путем сортировки списка (O(n log n)) или спуска внутренних узлов дерева, начиная со второй половины списка (O(n))."