Возможно ли удаление случайного узла из кучи?

Question

У меня есть ситуация, когда я хочу удалить случайный узел из кучи, какой выбор у меня есть? Я знаю, что мы можем легко удалить последний узел и первый узел кучи. Однако если мы скажем удалить последний узел, то я не уверен, правильно ли определено поведение для удаления случайного узла из кучи.

, например

_______________________
|X|12|13|14|18|20|21|22|
------------------------

Таким образом, в этом случае я могу удалить узлы 12 и 22, это определено, но я могу, например, удалить случайный узел, например, скажем 13, и все же каким-то образом поддерживать полное свойство дерева кучи (наряду с другими свойствами)?

Answer 1

Я предполагаю, что вы описываете двоичную кучу, поддерживаемую в массиве, с инвариантом, равным A[N] <= A[N*2] и A[N] <= A[N*2 + 1] (мин-куча).

Если да, то подходЧтобы удаление было простым: замените удаленный элемент последним элементом и выполните отжим, чтобы убедиться, что он оказался в нужном месте.И, конечно же, уменьшите значение переменной, содержащей общее количество записей в куче.

Кстати, если вы работаете с примерами кучи, я считаю, что лучше использовать примеры, которые не имеют общего порядка,В определении кучи нет ничего, что требует (например) A[3] <= A[5], и легко ввести в заблуждение, если ваши примеры имеют такой порядок.

Answer 2

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

3, 10, 4, 15, 20, 6, 5.

Теперь, если я удаляю элемент 15, куча становится: 3, 10, 4, 5, 20, 6

Это делает кучу несовместимой из-за того, что 5 является потомком 10.

Причина, по которой я думаю, что случайное удаление не сработает, заключается в том, что вы можете заменить внутренний узел (вместо корня или листа) в куче, и, таким образом, есть два пути (родители и дети) к heapify (как по сравнению с 1 путь в случае pop() или insert()). Пожалуйста, дайте мне знать, если я что-то здесь упустил.