Описание тега fibonacci-heap
Куча Фибоначчи - это реализация очереди с приоритетами, которая поддерживает вставку, слияние, поиск-мин и уменьшение ключа с амортизированным O(1), а также амортизированное удаление и извлечение O(log n). При реализации с кучей Фибоначчи алгоритм Дейкстры и алгоритм Прима можно заставить работать за O(E + V log V).
2
ответа
Является ли FibonacciHeap мини-кучей? Как найти Макс, используя FibonacciHeap?
Мой Java-проект состоит в том, чтобы использовать кучу Макса Фибоначчи для поиска самых популярных хэштегов. Запись может быть такой: #saturday 5 #sunday 3 #saturday 10 #monday 2 #reading 4 #playing_games 2 3 Но в куче Фибоначчи есть только функция …
07 окт '16 в 20:53
1
ответ
Как отслеживать узлы в дереве, используя хеш-таблицу?
Я пытаюсь реализовать кучу Фибоначчи, и мне необходимо отслеживать ее узлы для последующих операций. Для непосвященных куча Фибоначчи может рассматриваться как дерево m-степени или набор деревьев с указателем на максимальный узел в структуре. Древов…
14 ноя '16 в 21:35
1
ответ
Фибоначчи против Бинарное повышение производительности кучи в методе Fast Marching
Я сейчас этот вопрос задавал много раз. Тем не менее, я не могу найти решение для моей конкретной проблемы. Я реализовал метод быстрого марширования (очень похожий на Дейкстру) в C++11 и два разных варианта: с кучей Фибоначчи и двоичной кучей. Для э…
08 апр '14 в 12:34
3
ответа
Как реализовать алгоритм Прима с кучей Фибоначчи?
Я знаю алгоритм Прима и знаю его реализацию, но всегда пропускаю часть, которую хочу сейчас спросить. Было написано, что реализация алгоритма Прима с кучей Фибоначчи O(E + V log(V)) и мой вопрос: что такое куча Фибоначчи? Как это реализовано? А такж…
28 янв '11 в 06:30
3
ответа
Java: использование кучи Фибоначчи для реализации алгоритма Дейкстры
Новое здесь, но в течение некоторого времени скрывалось как гость:) Итак, я пытался сделать алгоритм кратчайшего пути Дейкстры, используя кучу Фибоначчи (в Java). После некоторых поисков мне удалось наткнуться на две готовые реализации, представляющ…
13 мар '13 в 17:26
1
ответ
Как реализовать уменьшение ключа в куче Фибоначчи для запуска в O(1) амортизированное время?
Как можно получить амортизированную сложность O(1) в операции уменьшения ключа в куче Фибоначчи? Простое нахождение узла в куче Фибоначчи, содержащей элемент, занимает O(n) времени с использованием BFS, что делает невозможным получение O(1) амортизи…
22 окт '13 в 07:23
1
ответ
Анализ размера кучи Фибоначчи (x) в CLRS имеет недостаток?
Во 3-м издании CLRS "Введение в алгоритмы", стр.525, когда анализируется нижняя граница размера (x), есть предложение, которое я цитирую как "поскольку добавление дочерних элементов в узел не может уменьшить размер узла, значение Sk увеличивается мо…
03 сен '11 в 06:32
0
ответов
Кучи Фибоначчи - как сохранить указатель на значение узла?
У меня есть график с 4 узлами, где матрица смежности выглядит следующим образом: Числа внутри указывают веса. ____1___2___3___4__ 1 | | 10| 5 | 1 ___________________ 2 |10 | | | ___________________ 3 | 5 | | | ___________________ 4 | 1 | | | _______…
01 фев '17 в 06:37
0
ответов
Повысить кучу Фибоначчи
Я искал код форсированной кучи Фибоначчи, и во многих местах я видел переменную под названием _id типа ID (часть шаблона) используется следующим образом:get(_id, d), где d имеет тип T&, где T является частью шаблона. Какова цель этого и что буде…
11 фев '14 в 04:28
1
ответ
Какова интуиция за структурой данных кучи Фибоначчи?
Я прочитал статью в Википедии о кучах Фибоначчи и прочитал описание структуры данных в CLRS, но они не дают интуитивного представления о том, почему эта структура данных работает. Почему кучи Фибоначчи спроектированы такими, какие они есть? Как они …
22 окт '13 в 03:36
2
ответа
Каковы наихудшие временные границы для каждой операции в куче Фибоначчи?
Кучи Фибоначчи эффективны в амортизированном смысле, но насколько они эффективны в худшем случае? В частности, какова временная сложность наихудшего случая каждой из этих операций в куче Фибоначчи с n-узлом? найти мин удалить-мин вставить снижение к…
14 фев '16 в 20:16
1
ответ
Проблема с кучей Фибоначчи
Я работаю над реализацией Fibonacci Heap в Java уже около недели. Это реализация, основанная на книге CLRS. Я хотел узнать, получу ли я какое-либо повышение производительности, используя его в стороннем проекте, над которым я работаю, по сравнению с…
30 авг '09 в 21:12
1
ответ
Есть ли в Haskell очередь приоритетов на основе кучи Фибоначчи?
Есть ли в Haskell очередь кучи / приоритета Фибоначчи? (Или даже асимптотически лучше?) В этом вопросе я нашел список различных реализаций очередей с приоритетами, но не смог найти, удовлетворяет ли какая-либо из них амортизированному времени выполн…
29 май '13 в 09:39
1
ответ
Продвиньте узел после того, как уже потеряли 2 или более детей
В decrease-key операция кучи Фибоначчи, если она может потерять s > 1 потомки, прежде чем вырезать узел и объединить его с корневым списком (продвинуть узел), это изменит общую сложность во время выполнения? Я думаю, что нет никаких изменений в с…
16 авг '13 в 16:59
1
ответ
Кучи Пелла, точно так же, как кучи Фибоначчи
Есть ли какая-нибудь куча, основанная на последовательности Пелла (или числе Пелла) вместо числа Фибоначчи (например, кучи Фибоначчи)?
10 авг '11 в 18:53
1
ответ
Почему мы проводим амортизированный анализ для кучи Фибоначчи?
В Фибоначчи кучи для всех операций анализа амортизируются по своей природе. Почему у нас не может быть нормального анализа, как в случае биномиальной кучи.
16 сен '16 в 03:22
1
ответ
Почему куча Фибоначчи хранит глобальный счетчик узлов?
Я читал, что в куче Фибоначчи хранится глобальный счетчик узлов, но я не понимаю, почему. Я даже нашел реализацию, которая имела счетчик, но не использовал его вообще.
23 ноя '13 в 23:19
0
ответов
Как куча Фибоначчи увеличивает эффективность алгоритма Прима
Я знаю алгоритм Прима и кучу Фибоначчи, но мой вопрос: как куча Фибоначчи повышает эффективность алгоритма по сравнению с реализацией очереди с минимальным приоритетом на основе списка массивов
16 авг '17 в 06:29
2
ответа
Где-нибудь на практике используются кучи Фибоначчи или очереди Бродала?
Кучи Фибоначчи используются на практике где-нибудь? Я посмотрел вокруг на SO и нашел ответы на связанные вопросы (см. Ниже), но ничего, что на самом деле вполне отвечает на вопрос. Есть хорошие реализации куч Фибоначчи, в том числе в стандартных биб…
11 июн '15 в 13:46
0
ответов
Как уменьшить временную сложность MST с помощью операции объединения кучи Фибоначчи?
Я ищу линейную временную сложность MST. Я пытаюсь выполнить это, используя кучу Фибоначчи как ее объединение и нахожу, что минимальная операция занимает постоянное время. Есть ли какая-нибудь ссылка, чтобы уменьшить временную сложность MST? Пожалуйс…
17 окт '18 в 14:23