Как увеличить минимальную кучу на основе массива после удаления минимальной?

Как бы я «упаковал» минимальную кучу на основе массива в java после вызова функции удаления min (это просто берет элемент с индексом 1 и удаляет его, а затем заменяет его последним элементом в массиве). Я не понимаю, как мне снова поместить массив в минимальную кучу после того, как произошло удаление min.

Индекс 0 всегда остается пустым в минимальном массиве кучи. Индекс родителя — i/2, правого потомка — 2i + 1, а левого потомка — 2i.

Любая помощь будет высоко оценена, спасибо, ребята!


java arrays heap min-heap
person Vimzy    schedule 31.10.2014    source источник

Ответы (1)


arrow_upward
1
arrow_downward

Возьмите последний элемент и скопируйте его на первую позицию. Уменьшите размер кучи на единицу и вызовите heapify() для первого элемента. Куча должна восстановить себя. Это имеет сложность O (log n)

Min-Heapify-Down (Array A, int i):
    left ← 2i
    right ← 2i + 1
    smallest ← i

    if left ≤ heap_length[A] and A[left] < A[smallest] then:
        smallest ← left
    if right ≤ heap_length[A] and A[right] < A[smallest] then:
        smallest ← right

    if smallest ≠ i then:
        swap A[i] ↔ A[smallest]
        Min-Heapify-Down(A, smallest)
person isklenar    schedule 31.10.2014
comment
Как бы выглядел код heapify для этого? - person Vimzy; 31.10.2014
comment
Это тот же метод heapify(), который вы используете при построении кучи. - person isklenar; 31.10.2014
comment
Дело в том, что heapify, который я использовал при построении кучи, использует родителя в качестве компаратора, поэтому с чем бы я сравнил новый элемент индекса 1, поскольку у него нет родителя. Вот что меня смущает. - person Vimzy; 31.10.2014
comment
@Vimzy Похоже, вам нужно посмотреть на разницу между процедурами heapify-up и heapify-down. en.wikipedia.org/wiki/Binary_heap - person Sneftel; 31.10.2014
comment
Как упоминал @Sneftel, вам нужно использовать heapify-down. Код в статье в Википедии предназначен для максимальной кучи. Вам просто нужно изменить его для работы с минимальной кучей. - person isklenar; 31.10.2014
comment
Можем ли мы написать модифицированный здесь? Возможно, это поможет и будущим читателям! - person Vimzy; 31.10.2014
comment
Я взял код из википедии и модифицировал его для минимальной кучи. Прошло много времени с тех пор, как я реализовал двоичную кучу, поэтому я надеюсь, что не сделал никаких ошибок. - person isklenar; 31.10.2014
comment
Что мы устанавливаем последнему элементу после того, как присвоим ему индекс 1? Ставим ли мы его на 0? - person Vimzy; 31.10.2014
comment
2 варианта. Либо установите его в Integer.MAX_VALUE (или MAX_VALUE из типа данных, который вы используете). Это работает для примитивных типов или для объектов, у которых есть какое-то MAX_VALUE. Однако если в кучу будет вставлено допустимое значение MAX_VALUE, это может вызвать проблемы. Другой вариант — сохранить переменную heapSize и просто уменьшить ее на единицу. heapify() (и другие методы) должны проверять heapSize и убедиться, что они не выходят за пределы. Второй вариант намного лучше, но немного сложнее. - person isklenar; 31.10.2014