Изменения

Чтобы упростить операцию <tex>decreaseKey</tex> можно написать кучу на основе [[АВЛ-дерево | сбалансированного бинарного дерева поиска]]. Тогда просто удалим вершину и добавим ее обратно уже с новым ключом. Асимптотика таких преобразований <tex>O(\log n)</tex>. Если же делать с бинарной кучей, то вместо операции <tex>decreaseKey</tex>, будем всегда просто добавлять вершину с новым ключом, а если из кучи достали вершинус ключом, которая значение которого больше чем у нее уже есть в деревестоит, просто игнорировать. Асимптотика операций в этом случае останется такой же — <tex>O(\log n)</tex> т.к. вершин Вершин в куче будет не больше чем <tex>n^2</tex>, следовательно, все операции будут операция <tex>extractMin</tex> будет выполняться за <tex>O(\log n^2)</tex>, что равно <tex>O(\log n)</tex>. Максимальное количество вершин, которое мы сможем достать, равняется количеству ребер, то есть <tex>m</tex>, поэтому общая асимптотика останется прежней — <tex>O(m \log n)</tex>.