хочу обновить связанный список до приоритетной кучи, но мне нужно удалить по значению

Question

Моя структура данных требует трех операций:

• вставить элемент в произвольном месте в порядке
• найти и удалить наименьший элемент
• (редко) удалить элемент с помощью некоторого ключа, возвращенного во время вставки

Существующий код представляет собой односвязный список и выполняет линейный поиск, чтобы найти точку вставки. O (n).

Поиск и удаление наименьшего элемента тривиален: снимите и утилизируйте головную тягу. O (1).

Вставка возвращает указатель на ссылку, и вызов удаления удаляет этот указатель. Если бы это был двойной список, ссылка могла бы быть просто удалена. O (1). Увы, список односвязный, и в списке ищется узел этого адреса, поэтому это O (n). Этот поиск дорог, но в некоторых случаях он позволяет обнаружить попытку удаления узла дважды: попытка удаления узла, которого нет в списке, не найдет его, поэтому ничего не будет делать, кроме как сгенерировать предупреждение в журнале , С другой стороны, узлы хранятся в пуле памяти LIFO, поэтому, вероятно, будут использоваться повторно, поэтому случайное повторное удаление узла может вместо этого удалить некоторый другой узел.)

OK, с кучей , вставка O (log n). Удаление минимума - O (log n). И то, и другое просто.

Но как насчет удаления по ключу? Если я храню кучу в массиве, это в основном линейный поиск, O (n). Я перемещаю элементы в куче, чтобы сохранить свойство кучи (пузырясь вниз и вверх по мере необходимости), поэтому я не могу просто использовать адрес узла. Кроме того, если вы не примете фиксированный максимальный размер, вам нужно перераспределить массив, который обычно перемещает его.

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

Учитывая дополнительные накладные расходы по выделению неподвижных узлов по отдельности и обновлению их поля индекса массива, звучит так, как будто это может быть больше, чем какое-то очень редкое количество линейных поисков. OTOH, преимущество сохранения узлов отдельно от кучи массива состоит в том, что быстрее менять местами указатели, чем целые узлы (которые в моем случае могут быть 32 байта или более).

Любые более простые идеи?

Answer 1

OK. Вы можете сохранить в памяти:

• Ваши структуры данных, содержащие полезную нагрузку и приоритет, динамически распределяются. Адрес структуры (указатель): removal key.
• Сохранять и поддерживать двоичную кучу, содержит pointers для этих структур данных. Но, сложите элементы в соответствии с приоритетами, содержащимися внутри структур, указателями.

Таким образом, ваши алгоритмы:

• Вставка: Создать структуру данных, развернуть указатель на куча, перебалансировать кучу: Log (N)

• Удалить последний: взять последний элемент из кучи, удалить структуру, удалить последний элемент из кучи, перебалансировать кучу: Log (N).

• Удалить случайный элемент: Получить указатель на элемент, по указателю получить приоритет, найти в куче этот элемент по приоритету: Log (n). Удалить структуру, удалить указатель из кучи. Перебалансируйте кучу - снова Log (N).

Answer 2

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

Куча - это куча указателей на эти узлы.

Узлы данных имеют целое число без знака, которое содержит текущий массив смещение указателя на них.

Когда мы перемещаем указатель (из-за операции кучи, такой как вставка или удалить) мы обновляем его индекс узлов. Например, если мы определяем, что наш ключ имеет более высокий приоритет, чем наш родитель, мы перемещаем нашего родителя в нашу текущую позицию следующим образом:

apnode[i] = apnode[iParent];
apnode[i]->iOffset = i;

Вставка данных с любым ключом и удаление узла с самым высоким приоритетом ключ, работает нормально. Оба являются O (log n).

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

Дополнительные издержки для поддержки этого случайного удаления равносильны установке этого смещения. Это всего лишь одна строка кода, но, с другой стороны, значительно увеличивает количество затронутых строк кэша по сравнению с кучей указателей без этой функции. С другой стороны, куча, вероятно, значительно быстрее для кучи указателя, чем на самом деле элементы массива быть самими узлами.

---

Почти полностью вне топики c, но очень полезно для любого, кто читает this:

Кажется, что во всех учебниках операции с кучей представлены следующим образом: добавьте свой элемент в конец кучи, а затем поменяйте местами, чтобы сложить его в нужное место. Однако каждый из этих обменов - это три инструкции. Вместо этого более эффективно рассматривать указатель на конец кучи в качестве места назначения-кандидата (CD) для новых данных, но пока не записывать его там.

Затем сравните ключ новых данных с родительским. Если новые данные имеют более низкий или равный приоритет, запишите их на CD и готово. В противном случае просто скопируйте родителя на CD, и адрес родителя станет новым CD. Повторение. Это сокращает фактические перемещения данных на 2 / 3rds.