Вопрос:

Как удалить произвольный элемент из стандартной кучи в c ++?

c++ heap

5663 просмотра

4 ответа

41 Репутация автора

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

vector<HeapEntry*> myHeap = vector<HeapEntry*>();
fillHeap(myHeap, someData);
make_heap(myHeap.begin(), myHeap.end());
while (!myHeap.empty())
{
    HeapEntry* hp = myHeap.front();
    HeapEntry* neighbor = hp->getNeighbor();
    if (someCondition)
    {
        remove(myHeap, neighbor);
    }
    //more processing of hp
}

И функция удаления:

void remove(vector<HeapEntry*> myHeap, HeapEntry* toRemove)
{
    for (it = myHeap.begin(); it != myHeap.end(); it++)
    {
        if (*it == hp)
        {
            myHeap.erase(it);
            break;
        }
    }
    make_heap(myHeap.begin(), myHeap.end());
}

Это работает и дает правильный вывод. Но он медлителен до чертиков: 2 минуты для обработки файла размером 40 КБ (размер кучи линейный по размеру файла). В любом случае это должно быть более эффективным.

Функция удаления в итоге вызывается примерно n раз, где n - размер кучи. Таким образом, наличие этого линейного поиска делает весь алгоритм O (n ^ 2). Я думаю, что это проблема, и я считаю, что это может работать в O (n * log (n)).

Моя цель - сделать функцию удаления за O (log (n)). Что-то вроде:

  • Идите прямо к целевому элементу
  • Переключите его с последним элементом
  • pop_heap (myHeap.begin (), myHeap.end ()); myHeap.pop_back ();
  • make_heap (myHeap.begin (), myHeap.end ());

Я не совсем уверен, как это реализовать (я почти не знаком с кучей STL). Кто-нибудь знает, как это сделать без выполнения линейного поиска?

Автор: yan Источник Размещён: 24.09.2012 06:45

Ответы (4)


1 плюс

32098 Репутация автора

Философия stl заключается в том, чтобы сначала отразить ваш алгоритм, а затем выбрать структуру данных. Вы делаете это наоборот.

Если вы планируете удалять элементы из вашей структуры данных в «случайном» порядке, вы, вероятно, лучше с priority_queueили даже связаны list. (Однако будьте осторожны: итераторы могут быть недействительными после удаления из некоторых контейнеров stl).

Автор: xtofl Размещён: 24.09.2012 06:55

5 плюса

127692 Репутация автора

Простой подход состоит не в том, чтобы удалить элементы, которые вы хотите удалить. Вместо этого вы должны поддерживать приоритетную очередь для определения следующего элемента max и std::set<HeapEntry*>удаленного элемента. При получении элемента max вы проверяете, есть ли он в наборе удаленных элементов, и вы просто удаляете его из кучи, пробуя следующий элемент. В зависимости от количества потенциально удаленных элементов может потребоваться также удалить элемент из набора удаленных элементов при удалении его из кучи.

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

Другой альтернативой может быть использование очереди приоритетов на основе узлов для эффективного поиска позиции узла в куче. Например, Boost предоставляет кучу Фибоначчи как часть библиотеки графов ускорения. Вы можете отслеживать положение элемента там. Тем не менее, кучи на основе узлов имеют тенденцию работать медленнее на практических проблемах размера из-за их издержек при перестановке элементов.

Автор: Dietmar Kühl Размещён: 24.09.2012 07:36

1 плюс

41 Репутация автора

Спасибо за все ваши ответы. Я решил пойти с подходом, который фактически удаляет HeapEntries, когда они больше не действительны. На самом деле я попытался добавить действительный флаг в HeapEntry, и я думаю, что это сработало бы, если бы не некоторые другие ошибки, которые я с тех пор исправил. Во всяком случае, вот как я в конечном итоге решить это.

Чтобы повторить, мне нужна была возможность удалить элемент из кучи, учитывая только указатель на этот элемент. Проблема была в том, что указатель не сказал мне ничего о позицииэлемента в куче. Итак, я решил сохранить позицию, обновлять ее при каждом перемещении элементов и написать функцию для удаления из кучи с заданной позицией. Проще говоря, куча хранится в виде массива, а позиции элементов определяют отношения родитель / потомок. Родитель элемента должен находиться на этаже местоположения ((myPos - 1) / 2), а его дочерние элементы должны находиться в позициях 2 * myPos + 1 и 2 * myPos + 2. Я понял, что могу написать функцию удаления (позиции) и, в то же время, меняя элементы для сохранения свойства кучи, можно также поменять их сохраненные позиции. Вот ссылка на результат, и он ускорил выполнение в 5 или 10 раз:

https://github.com/yankrasny/CC-Heap-with-random-delete

Автор: yan Размещён: 04.11.2012 08:42

0 плюса

1 Репутация автора

Я опоздал почти на 7 лет, но надеюсь, что это поможет кому-то еще. Несколько хороших вариантов были обсуждены выше, и я просто хотел бы добавить еще один.

Если вы используете сбалансированный BST (то есть set<HeapEntry*>), вы можете найти max и удалить элемент в O (log n). Это сделает весь ваш алгоритм O (n log n).

Примечание 1: если у вас есть дубликаты, используйте multisetвместо этого и удалите, используя <ms>.erase(<ms>.find(<obj>))для удаления только одно вхождение <obj>. <ms>.erase(<obj>)удаляет все вхождения <obj>.

Примечание 2: find max можно сделать O (1), используя грань, что если элемент удален, все итераторы, указатели и ссылки на другие элементы остаются действительными. ( источник )

Автор: Arsalan Jumani Размещён: 13.06.2019 06:25
Вопросы из категории :
32x32