Описание тега decrease-key
0
ответов
Как добиться времени O(log(n)) для уменьшения ключа в биномиальной куче
Почти в каждом месте, которое я читаю, утверждается, что уменьшение ключа в биноминальной куче занимает время O(log(n)). Хотя это имеет смысл, поскольку сама операция требует этого времени, они не учитывают поиск ключа, который должен быть уменьшен,…
20 май '18 в 20:36
1
ответ
Как реализовать уменьшение ключа в куче Фибоначчи для запуска в O(1) амортизированное время?
Как можно получить амортизированную сложность O(1) в операции уменьшения ключа в куче Фибоначчи? Простое нахождение узла в куче Фибоначчи, содержащей элемент, занимает O(n) времени с использованием BFS, что делает невозможным получение O(1) амортизи…
22 окт '13 в 07:23
2
ответа
Упорядоченный словарь, поддерживающий ключ уменьшения?
Многие очереди с быстрым приоритетом (такие как куча Фибоначчи и куча сопряжения) поддерживают операцию уменьшения ключа, которая принимает элемент, уже сохраненный в очереди приоритетов, и эффективно снижает его приоритет. В случае кучи Фибоначчи и…
05 янв '13 в 19:17
1
ответ
Реализация биномиальной кучи в Python 2.7
Я ищу реализацию Binomial Heap на Python и заметил, что в кодах не реализовано снижение ключа. Почему в Binomial Heap никто не реализует снижение ключа?
10 сен '15 в 12:57
1
ответ
Как заставить ключ уменьшения в биномиальной куче работать во время логарифма
Интерфейс, предоставляемый книгой "Введение в алгоритм" уменьшения ключа в биномиальной куче: BINOMIAL-HEAP-DECREASE-KEY (H,x,k), где H - указатель на первый корень дерева, x - это "индекс" узла, ключ которого должен быть уменьшен до k. И сложность …
13 ноя '13 в 06:25
2
ответа
Почему в Java Priority Queue отсутствует метод Change Priority?
Мне было интересно, почему Java Priority Queue не поддерживает ChangePriority. Я где-то читал (без подробностей), что удаление ChangePriority позволяет использовать более эффективную реализацию, но я понятия не имею, как это возможно - двоичная куча…
23 июн '15 в 10:45
4
ответа
Реализовать уменьшение ключа в очереди приоритетов STL C++
Я пытаюсь реализовать Алгоритм Прима, и для этого мне нужно иметь метод lowerKey для приоритетной очереди (чтобы обновить значение ключа в приоритетной очереди). Могу ли я реализовать это в очереди приоритетов STL? Если это поможет, вот алгоритм, ко…
19 янв '13 в 09:09
3
ответа
Почему уменьшение ключа в алгоритме Дейкстры занимает время O(logN)?
Для обновления части, for all neighbors w of u: if dist[w] > dist[u] + l(u,w) dist[w] = dist[u] + l(u,w) prev[w] = u decreasekey(H,w) Здесь w - это идентификатор узла, я думаю, что это должна быть пара (ID, ключ), ключом которого является dist[ID…
14 ноя '13 в 05:45
1
ответ
Уменьшить работу в куче Фибоначчи, повысить
Я пытаюсь использовать в своей реализации кучу Фибоначчи от boost, но моя программа падает, когда я вызываю функцию lower, вот пример (W - простой класс): struct heap_data { boost::heap::fibonacci_heap<heap_data>::handle_type handle; W* payloa…
26 май '15 в 19:09
3
ответа
Как реализовать операцию уменьшения ключа O(logn) для приоритетной очереди на основе минимальной кучи?
Я работаю над приложением, которое демонстрирует алгоритм Джикстры, и чтобы использовать его, мне нужно восстановить свойство кучи, когда значение моих элементов уменьшается. Проблема, связанная со сложностью, состоит в том, что когда алгоритм измен…
09 июн '13 в 11:21
0
ответов
Почему выделенная память кучи уменьшается с 4G до 3.86G?
Tomcat работает на виртуальной машине. Я наблюдал за внезапным уменьшением выделенной памяти кучи JVM с 4G до 3.86G. Это вызывает FULL GC. Я хочу знать, почему и когда JVM это делает?
30 апр '19 в 01:13
2
ответа
как расположить массив в порядке убывания
У меня есть простой код для перебора всех элементов в диапазоне for i in range(5,10): print(i) #output 5 6 7 8 9 Теперь можно ли повторять одни и те же элементы от 10 до 5 в порядке убывания? Изменение диапазона в приведенном выше коде с 10 на 5 не …
20 май '22 в 15:36
0
ответов
Что такое операция уменьшения ключа для двусвязного списка?
Я наткнулся на это описание структуры данных при переполнении Gate: элементы хранятся в отсортированном двусвязном списке. Для операции удаления предоставляется указатель на удаляемую запись. Для операции уменьшения ключа предоставляется указатель н…
02 сен '22 в 05:34