Итак, вот вопрос:
Предположим, что в качестве минимальной кучи используются родительские указатели, так что каждый узел содержит указатель на своего родителя, а корень имеет нулевой указатель. Учитывая указатель на узел, который не является корнем дерева, содержащий ключ max в куче, какова сложность удаления?
Ответ O (1), но для меня это не имеет смысла. Поскольку кучи всегда сбалансированы, вы не можете заменить удаленный узел соседним узлом, вам нужно масштабировать длину дерева O (log N), чтобы найти последний введенный узел в дереве, правильно? Почему нет ответа на этот вопрос O (журнал N)?
например:
куча вставлена в порядке 1, 100, 2, 3, 4, 5, давая 1 в качестве корневого узла, 100 и 2 и дочерние элементы, 3 и 4 как дочерние элементы 100 и 5 как дочерние элементы 2.
удаление 100 потребовало бы замены на 5, что занимает O (log N) времени для доступа, верно?