Есть ли куча или структура, подобная куче, которая работает с указателями, другими словами, узлами не в массиве?

Question

В настоящее время у меня есть двойной список объектов в порядке убывания.(Список навязчив - указатели на объекты.) У меня очень ограниченный набор операций:

1. добавить узел с максимально возможным ключом
2. удалить узел смаксимально возможный ключ (неважно, какой)
3. удалить узел с ключом 0 (неважно, какой)
4. инкрементный ключ узла с наибольшим текущим ключом (не имеетнезависимо от того, какой из них)
5. ключ декремента любого заданного узла, ключ которого выше 0

Операции 1-4 будут постоянным временем, но операция 5 будет O(n), где n = количество узлов с одинаковым значением ключа.Это связано с тем, что такие узлы при увеличении необходимо перемещать за их братьев и сестер с одинаковым значением ключа и размещать после этого диапазона.И обнаружение, что место повторной вставки будет O (n).

Я думал о куче (куча сортировки, а не куча malloc) как решение, где наихудший случай будет O (log n) (где n= количество узлов).Тем не менее, основываясь на моих воспоминаниях и на том, что Google находит меня, кажется, что он неизменно реализован в массиве, а не в двоичном дереве.Итак:

Вопрос: существует ли реализация кучи, которая использует указатели в виде двоичного дерева, в отличие от массива, который поддерживает O () типичной реализации массива?

Answer 1

Один из распространенных способов сделать это - использовать кучу на основе массива, но:

• В куче хранятся указатели на узлы;
• В каждом узле, где вы храните своииндекс в куче;и
• Всякий раз, когда вы меняете элементы в куче, вы обновляете индексы в соответствующих узлах;

Это сохраняет сложность всех операций кучи и стоит около 1,5 указателей и 1.целое число на узел.(дополнительные .5 из-за способа реализации растущих массивов).

В качестве альтернативы, вы можете просто связать узлы вместе в дерево с указателями.Однако для поддержки требуемых операций требуется 3 указателя на узел (родитель, слева, справа)

Оба способа работают нормально, но реализация массива проще, быстрее и использует немного меньше памяти.

ETA:

Я должен отметить, что если вы используете указатели, то вы можете использовать разные виды кучи.Куча Фибоначчи позволит вам уменьшить значение узла в амортизированном постоянном времени.Это довольно сложно, хотя и медленно на практике: https://en.wikipedia.org/wiki/Fibonacci_heap

Answer 2

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

Решение 1: структура данных с амортизированными O (1)

Было найдено решение с использованием амортизированных O (1) всех необходимых операций.

Это просто двойной список списков двойной связи. «Основные» узлы двойного связанного списка называются родителями, и у нас есть не более одного родителя на значение ключа. Родительские узлы хранят двойной список дочерних узлов с одинаковым значением ключа. Каждый ребенок дополнительно указывает на своего родителя.

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

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

3. удалить (любой) узел со значением 0: Те же операции.

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

5. уменьшить значение любого узла выше 0: Если узел является дочерним, удалите его из дочернего списка, затем либо добавьте в дочерний список наследника родителя, либо в качестве нового узла после родительского. Родитель без детей: если у преемника в главном списке все еще есть меньший ключ, все готово. В противном случае удалите его и добавьте в качестве наследника наследника. Родитель с детьми: то же самое, но помогите главному ребенку занять его место. Это O (n) , где n = количество узлов данного размера, потому что вы должны изменить родительский указатель для всех дочерних элементов. Однако, если коэффициенты выбранного узла для декремента, являющегося родительским узлом всех узлов данного размера, равны 1 / n, это амортизируется до O (1).

Основным недостатком является то, что у нас по логике есть 7 разных указателей для каждого узла. Если это в роли родителя, нам нужен предыдущий и следующий родитель, а также ребенок с головой и хвостом. Если это в роли ребенка, нам нужен предыдущий и следующий ребенок, и родитель. Они могут быть объединены в две альтернативные подструктуры с 4 и 3 указателями, что экономит память, но не процессорное время (исключая, возможно, необходимость обнуления неиспользуемых указателей для чистоты). Обновление их всех не будет быстрым.

Решение 2: Хлопок достаточно хорош

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

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