Изменения

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