Удаление случайного элемента из кучи

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

  1. Найдите индекс ключевого элемента, который вы хотите удалить
  2. Поменяйте местами этот элемент с последним элементом, чтобы ключ стал последним элементом
  3. Повторно сложите, начиная с исходного индекса ключа (который вы теперь поменяли местами с последним элементом)
  4. Уменьшить размер кучи на 1

Итак, код будет выглядеть

static void delete(int[] a, int key)
    {
        int i = 0;
        for(i = 0;i<a.length;i++)
        {
            if(a[i] == key)
                break;
        }
        swap(a, i, a.length-1);

        max_heapify_forheapsort(a, i, a.length-2);
    }

static void max_heapify_forheapsort(int[] a, int i, int limit)
    {
        int left = (2*i)+1;
        int right = (2*i) + 2;
        int next = i;

        if(left <= limit && a[left] > a[i])
            next = left;
        if(right <= limit && a[right] > a[next] )
            next = right;

        if(next!=i)
        {
            swap(a, next, i);
            max_heapify_forheapsort(a, next, limit);
        }
    }
Источник

2 ответа

Решение

Конечно, вы можете удалять элементы из кучи с помощью операций sift-up или sift-down, как вы предлагаете. (Аналогичным образом можно изменить ключ любого элемента в куче и использовать операции sift-up или-down для восстановления свойства кучи.)

Сложность в том, что вы быстро заявили в начале: "Найдите индекс". Наивная реализация требует O(n), чтобы сделать это, и это убивает эффективность кучи. Что люди имеют в виду, когда говорят "вы не можете удалить", так это то, что при наивной реализации вы не можете эффективно удалить.

К счастью, нетрудно найти индекс O(1). Просто поддерживайте "обратную карту" параллельно с массивом кучи, например, карту хеш-функции от объектов к индексам массива кучи. Эту карту легко обновить, не добавляя асимптотическую сложность ни к одной из операций кучи, и с ее помощью, как вы отметили, удаление имеет сложность O(log n). Сдвиг вверх / вниз доминирует в поиске карты, чтобы найти индекс.

Если вам интересна протестированная реализация, вот та, где куча содержит индексы в другом массиве объектов. Поэтому обратная карта реализована в виде массива q->locs[k], который является индексом элемента кучи, который содержит k (который является индексом в таблице объектов).

Многие проблемы в информатике могут быть решены путем добавления уровня косвенности!

редактировать

Поскольку OP спросил о том, почему для удаления может потребоваться sift up, рассмотрите минимальную кучу

          1
    20          2 
 30    40    3     4

Мы хотим удалить 30, поэтому переместим 4 (последний элемент массива) на свою позицию:

          1
    20          2 
 4     40    3

Ясно, что требуется просеять.

Источник

Если это Minheap,

  • Сохраните удаляемый элемент в переменной.
  • Замените элемент наименьшим целым числом. Heapify До корня.
  • Удалите рут, чтобы Heapify вниз, чтобы сохранить свойство кучи.
  • Верните сохраненную переменную. Источник - GeeksforGeeks.
Источник

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

Источник
Другие вопросы по тегам