реализовать уменьшающий ключ в биноминальной куче - PullRequest
1 голос
/ 15 октября 2011

в структуре биномиальной кучи мы знаем только указатель, который указывает на минимальный узел, но как я могу уменьшить ключ произвольного узла? в этом случае, прежде всего, я должен найти этот узел, а затем выполнить обмен с O (lgN) времени.

Я ищу в Интернете, и многие указывают, как уменьшить узел, но не упоминают, как уменьшить доступ к этому узлу.

Edit:

Я должен использовать указатели, которые указывают на каждый узел кучи.

1 Ответ

1 голос
/ 15 октября 2011

Может быть, я что-то здесь упускаю, но если у вас есть ключ к вашему «произвольному узлу», вы не могли бы просто использовать поиск времени O(lg n), чтобы найти его, а затем уменьшить его, используя алгоритм, который вы нашли в Интернете?

...