Как выполнить удаление k-го элемента в куче min-max?

Question

Мин-макс куча может быть полезна для реализации двусторонней очереди приоритетов из-за ее постоянного времени find-min а также find-max операции. Мы также можем извлечь минимальный и максимальный элементы в куче min-max за O (log₂ n) времени. Иногда, однако, мы также можем захотеть удалить любой узел в куче min-max, и это можно сделать в O (log₂ n), согласно статье, в которой были представлены кучи min-max:

...

Структура также может быть обобщена для поддержки операции Find(k) (определить k-е наименьшее значение в структуре) в постоянное время и операцию Delete(k) (удалить k-е наименьшее значение в структуре) в логарифмическом времени для любого фиксированного значения (или набора значений) k,

...

Как именно выполнить удаление k-го элемента в куче min-max?

Answer 1

Я не считаю себя "экспертом" в области алгоритмов и структур данных, но у меня есть детальное понимание бинарных куч, включая кучу min-max. См., Например, мою серию блогов о двоичных кучах, начиная с http://blog.mischel.com/2013/09/29/a-better-way-to-do-it-the-heap/. У меня есть реализация min-max, о которой я когда-нибудь расскажу.

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

Удаление произвольного узла в куче min-max принципиально не отличается от той же операции в куче max или min. Рассмотрим, например, удаление произвольного узла в минимальной куче. Начните с этой минимальной кучи:

      0
  4       1
5   6   2   3

Теперь, если вы удалите узел 5, у вас есть:

      0
  4       1
    6   2   3

Вы берете последний узел в куче, 3, и помещаете его в место, где 5 было:

      0
  4       1
3   6   2   

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

      0
  3       1
4   6   2   

Те же правила применяются для кучи мин-макс. Вы заменяете удаляемый элемент последним элементом из кучи и уменьшаете количество. Затем вы должны проверить, нужно ли его вздувать или просеять. Единственная сложность в том, что логика отличается в зависимости от того, находится ли предмет на минимальном уровне или максимальном уровне.

В вашем примере, куча, которая получается в результате первой операции (замена 55 на 31), недопустима, потому что 31 меньше, чем 54. Таким образом, вы должны разбить ее в кучу.

Еще одна вещь: удаление произвольного узла действительно является операцией log₂(n). Однако поиск удаляемого узла является операцией O(n), если у вас нет какой-либо другой структуры данных, отслеживающей, где находятся узлы в куче. Таким образом, в общем случае удаление произвольного узла считается O(n).

Answer 2

Что привело меня к разработке этого решения (которое я не уверен на 100% правильно), так это то, что я действительно нашел решение для удаления любого узла в куче min-max, но это неправильно.

Неправильное решение может быть найдено здесь (реализовано в C++) и здесь (реализовано в Python). Я собираюсь представить только что упомянутое неправильное решение Python, которое более доступно для всех:

Решение заключается в следующем:

def DeleteAt(self, position):
    """delete given position"""
    self.heap[position] = self.heap[-1]
    del(self.heap[-1])
    self.TrickleDown(position)

Теперь предположим, что у нас есть следующая min-max куча:

level 0                            10                        

level 1                92                       56           

level 2         41          54          23          11     

level 3      69    51    55    65    37    31

насколько я проверил, это допустимая куча min-max. Теперь предположим, что мы хотим удалить элемент 55, который в массиве на основе 0 будет найден по индексу 9 (если я правильно посчитал).

То, что сделало бы решение выше, просто поместило бы последний элемент в массиве, в данном случае 31, и поместило его в позицию 9:

level 0                            10                        

level 1                92                       56           

level 2         41          54          23          11     

level 3      69    51    31    65    37    55

он удалит последний элемент массива (который теперь равен 55), и результирующая куча min-max будет выглядеть так:

level 0                            10                        

level 1                92                       56           

level 2         41          54          23          11     

level 3      69    51    31    65    37 

и, наконец, это будет "просачиваться" из position (т.е. где сейчас у нас число 31).

"tricle-down" будет проверять, находимся ли мы на четном (или минимальном) или нечетном (или максимальном) уровне: мы находимся на нечетном уровне (3), поэтому "trickle-down" назовет "trickle-down-max", начиная с 31, но, поскольку у 31 нет детей, он останавливается (проверьте оригинальную статью выше, если вы не знаете, о чем я говорю).

Но если вы заметите, что это оставляет структуру данных в состоянии, которое больше не является минимально-максимальной кучей, потому что 54, который находится на четном уровне и поэтому должен быть меньше, чем его потомки, больше чем 31, один из его потомков.

---

Это заставило меня думать, что мы не могли просто смотреть на детей узла в position, но это мы также должны были проверить, что position вверх, что, возможно, нам тоже нужно было использовать "trickle-up".

В следующих рассуждениях пусть x быть элементом в position после того, как мы удалили элемент, который мы хотели удалить, и перед выполнением любых операций исправления. Позволять p быть его родителем (если есть).

Идея моего алгоритма действительно такова, и, более конкретно, основана на том факте, что:

1. Если x находится на нечетном уровне (как в примере выше), и мы обмениваем его с его родителем p, который находится на ровном уровне, который не нарушил бы никаких правил / инвариантов кучи min-max из нового x Положение вниз.

   • Те же рассуждения (я думаю) могут быть сделаны, если ситуация будет полностью изменена, т.е. x изначально был в четном положении, и он был бы больше, чем его родитель.

   • Теперь, если вы заметили, единственное, что может потребоваться исправить это то, что если x был обмен со своим родителем, и теперь он находится в четном (и соответственно нечетном) положении, нам может понадобиться проверить, меньше ли он (и соответственно больше), чем узел на предыдущем четном (и соответственно нечетном) уровне.

Это, конечно, не было полным решением для меня, и, конечно, я также хотел проверить, если предыдущий родитель x т.е. p, находится в правильном положении.

• Если p после обмена с x, находится на нечетном (и, соответственно, четном) уровне, это означает, что он может быть меньше (и соответственно больше), чем любой из его потомков, потому что ранее он был на четном (и соответственно нечетном) уровне. Итак, я подумал, что нам нужно "ручеек" здесь.

• Что касается того факта, если p находится в правильном положении по отношению к своим предкам, я думаю, что рассуждения будут аналогичны рассмотренным выше (но я не уверен на 100%).

Собрав все воедино, я нашел решение:

function DELETE(H, i):

    // H is the min-max heap array
    // i is the index of the node we want to delete
    // I assume, for simplicity, 
    // it's not out of the bounds of the array

    if i is the last index of H:
        remove and return H[i]
    else:
        l = get_last_index_of(H)

        swap(H, i, l)  

        d = delete(H, l)

        // d is the element we wanted to remove initially
        // and was initially at position i
        // So, at index i we now have what was the last element of H

        push_up(H, i)

        push_down(H, i)

        return d

Кажется, это работает в соответствии с реализацией кучи min-max, которую я сделал и которую вы можете найти здесь.

Также обратите внимание, что решение выполняется за время O (log ₂ n), потому что мы просто вызываем "push-up" и "push-down", которые запускаются в таком порядке.