Описание тега binomial-heap
Биномиальная куча - это тип структуры данных очереди приоритетов, реализованный в виде леса биномиальных деревьев. Биномиальные кучи поддерживают быструю вставку, удаление и слияние.
1
ответ
Подсчет количества узлов в биномиальной куче определенного уровня
У нас есть биноминальная куча, состоящая из 2016 узлов. Декомпозируя в двоичный файл, мы получаем 11111100000 Куча состоит из 6 веток с узлами 512 256 128 64 32 и 16. Но как мы можем рассчитать количество узлов на определенном уровне? Какова формула…
09 ноя '16 в 18:02
0
ответов
Ошибка сегмента с помощью Boost::Heap Handle
Новый (плохой) C++ программист здесь (поэтому, пожалуйста, не обращайте внимания на все несущественные ошибки / упрощения для удобства чтения): У меня постоянные проблемы при использовании маркеров Boost::heap. Обычно я либо сегментирую ошибку, либо…
22 фев '13 в 19:47
2
ответа
Правильная функциональная реализация на биномиальной куче
Я читаю Binomial Heap в чисто функциональных структурах данных. Реализация insTree функция меня сильно смутила. Вот набор кодов datatype Tree = Node of int * Elem.T * Tree list fun link (t1 as Node (r, x1, c1), t2 as Node (_, x2, c2)) = if Elem.leq …
31 окт '13 в 10:46
0
ответов
Как смещается псевдокод биномиального дерева?
То, что я не могу понять здесь, - то, как заявления были отступлены. Нормально, если и иначе, если должны быть одинаково отступ. Я хочу понять, как здесь они отступили. Везде объединение кода биномиального дерева имеет отступ только таким образом. М…
14 фев '18 в 18:50
0
ответов
Как добиться времени O(log(n)) для уменьшения ключа в биномиальной куче
Почти в каждом месте, которое я читаю, утверждается, что уменьшение ключа в биноминальной куче занимает время O(log(n)). Хотя это имеет смысл, поскольку сама операция требует этого времени, они не учитывают поиск ключа, который должен быть уменьшен,…
20 май '18 в 20:36
1
ответ
Реализация биномиальной кучи в Python 2.7
Я ищу реализацию Binomial Heap на Python и заметил, что в кодах не реализовано снижение ключа. Почему в Binomial Heap никто не реализует снижение ключа?
10 сен '15 в 12:57
0
ответов
Можете ли вы заметить что-то не так с этим объявлением boost::heap::binomial_heap?
У меня есть член с именем handle в классе Vertex моей реализации графа. Это объявлено так: boost::heap::binomial_heap<Vertex*,boost::heap::compare<VertComp> >::handle_type handle; ... Дескриптор взят из библиотеки boost:: heap, которую н…
27 апр '12 в 15:09
1
ответ
Если биномиальные кучи представлены в виде наборов деревьев, почему эта реализация имеет только одно дерево?
Эта статья в Википедии о биномиальных кучах говорит о том, что биноминальная куча - это набор биномиальных деревьев. Но эта реализация использует только одно дерево. Так что я в замешательстве - это реализация биноминальной кучи? Если так, то как эт…
24 май '15 в 14:26
1
ответ
Как заставить ключ уменьшения в биномиальной куче работать во время логарифма
Интерфейс, предоставляемый книгой "Введение в алгоритм" уменьшения ключа в биномиальной куче: BINOMIAL-HEAP-DECREASE-KEY (H,x,k), где H - указатель на первый корень дерева, x - это "индекс" узла, ключ которого должен быть уменьшен до k. И сложность …
13 ноя '13 в 06:25
3
ответа
В чем разница между двоичными кучами и биномиальными кучами?
Мне нужно знать основное различие между двоичными и биномиальными кучами независимо от их структурного различия, заключающееся в том, что двоичные кучи могут иметь только два дочерних элемента (представление дерева), а биномиальные кучи могут иметь …
02 июн '11 в 13:53
3
ответа
Несвязанные множества структур данных и биномиальных деревьев?
Может ли кто-нибудь объяснить, что такое структура данных Disjoint Sets, или, в качестве альтернативы, связать меня с видео YouTube или статьей, которая это хорошо объясняет. Я искал его несколько минут назад, и все, что я получил, было несколько ур…
12 дек '12 в 21:56
0
ответов
Как реализовать merge и del min в биноминальной куче
Я пытаюсь реализовать метод getmin,delmin и merge. Это то, что я сделал до сих пор, но это не работает. Мне также нужно изменить метод вставки? Метод вставки также работает только для положительных чисел. Класс BinomialNode использует Vector childs …
06 янв '19 в 17:52
1
ответ
Докажите, что количество биномиальных деревьев в биномиальной куче с n элементами не больше O(log n)
У меня проблемы с поиском хорошего доказательства этого утверждения. Я знаю, как определить количество биномиальных деревьев, определяется с помощью двоичного представления n. Например, 13 элементов - это 1101 в двоичном виде, 2^{3}+2^{2}+2^{0}, поэ…
18 фев '14 в 15:40
2
ответа
Когда было бы предпочтительнее реализовать приоритетную очередь с односвязным списком над кучей?
Недавно я только начал проект с некоторым кодом, который уже был написан. Я решил изучить его реализацию и обнаружил, что он реализовал приоритетную очередь с односвязным списком. Насколько я понимаю, SLL может заключаться в том, что, поскольку вам,…
20 июн '11 в 16:45
0
ответов
Печать содержимого биномиальной кучи в порядке возрастания / убывания
Учитывая, что биномиальная куча является набором биномиальных деревьев, у меня возникают трудности с пониманием того, как мы можем эффективно распечатать содержимое биномиальной кучи в порядке возрастания / убывания (в зависимости от того, является …
17 май '18 в 15:53
0
ответов
Следует ли объединять / объединять биномиальные кучи за один или два прохода?
Реализация Okasaki в Purely Functional Data Structures (стр. 22) делает это двумя: один для объединения леса и один для распространения переносов. Это кажется мне более сложным для анализа и, вероятно, медленнее, чем однопроходная версия. Я что-то п…
13 июл '12 в 00:34
1
ответ
Реализовать уменьшающий ключ в биноминальной куче
В структуре биномиальной кучи мы знаем только указатель, который указывает на узел min, но как я могу уменьшить ключ произвольного узла? в этом случае, прежде всего, я должен найти этот узел, а затем выполнить обмен с O(lgN) времени. Я ищу в Интерне…
14 окт '11 в 23:17
0
ответов
Как операция вставки имеет амортизированное время O(1) в биномиальной куче?
Википедия говорит, что операция вставки в биномиальной куче имеет амортизированное время O(1). Для одной операции вставки временная сложность составляет O(log n). Но как его амортизированное время становится O(1)?
06 окт '16 в 13:06
1
ответ
Вставить те же значения в биноминальную кучу
Я должен вставить некоторые значения в биноминальную кучу. Например, 25, 26, 24, 60, 65, 62. Это будет выглядеть следующим образом: Но тогда я должен вставить 25, 68, 65 в ту же кучу. Должен ли я вставить 25 снова или просто пропустить его, поскольк…
01 окт '14 в 07:25
1
ответ
Код рекурсивного биномиального дерева, не может сделать больше 5 шагов... почему?
function [y]=AmericanPutClassic (St,t) % S0 = 100; K = 100; r = 0.05; sigma = 0.3; T = 2; nsteps = 5; % St dt = T / nsteps; u=exp(sigma*sqrt(dt)); d=1/u; Pu=(exp(r*dt)-d)/(u-d); Pd=1-Pu; if t==T y=max(K-St,0); return elseif t<T upPrice=AmericanPu…
18 ноя '12 в 21:03