Бинарные кучи против д-арых куч
Я читал, что двоичные кучи быстрее при минимальных операциях удаления, а d-ary - быстрее при операциях с уменьшением приоритета (хотя я не понимаю, почему), но потом я также прочитал, что 4-куча быстрее при они оба по сравнению с двоичной кучей.
Так, когда я использую двоичную кучу, и когда я использую d-ary кучу? И как мне решить, какой d должен быть для кучки d-ary?
2 ответа
Здесь есть несколько различных факторов, которые, как я полагаю, позволяют сделать все ваши заявления правдивыми.
Чтобы понять, почему это так, давайте начнем с размышления о том, как работает ключ уменьшения в динамической куче (нам не нужно отдельно говорить о двоичных кучах, поскольку двоичная куча - это всего лишь двухрядная куча). Выполняя клавишу уменьшения, мы меняем приоритет узла в дереве, затем многократно меняем его родительский элемент до тех пор, пока он либо не достигнет корня дерева, либо его приоритет не станет меньше, чем приоритет его родителя. Количество раз, когда мы должны сделать обмен, в худшем случае определяется высотой d-ary кучи. Поскольку число узлов в каждом слое d-арной кучи растет экспоненциально в d раз на каждом шаге, высота d-арной кучи составляет O (logd n) = O (log n / log d). Это означает, что если вы увеличите значение d, высота d-ary-кучи уменьшится, поэтому клавиши уменьшения и вставки будут занимать меньше времени. Если вы подумаете об экстремальном случае, если у вас есть куча размером 10100, количество слоев в дереве будет примерно в 100 раз меньше, чем в двоичной куче, поэтому клавиша уменьшения или вставка будут примерно в 100 раз быстрее.,
С другой стороны, подумайте о том, как будет работать операция удаления очереди. Чтобы выполнить удаление, мы меняем последний лист на корень, затем многократно делаем следующее: мы сканируем все дочерние элементы текущего узла, и если какой-либо из них меньше текущего узла, мы меняем текущий узел на самый маленький из его детей. Каждая из этих итераций потребует O (d) общего сравнения, чтобы найти наименьший дочерний элемент, а количество итераций определяется числом слоев в дереве, которое мы видели ранее, равно O (log n / log d). Это означает, что стоимость очереди в динамической куче равна O (d log n / log d). Поскольку d растет намного быстрее, чем log d (фактически экспоненциально быстрее), при увеличении d асимптотическая - и фактическая - стоимость очереди начинает расти. Например, в 10100- членной куче вам, возможно, придется сравнивать каждый узел с 10100 дочерними элементами на каждом шаге, что займет очень много времени! Следовательно, d-арные кучи, поскольку d становится все больше и больше, имеют тенденцию иметь гораздо более медленные очереди, чем двоичные кучи.
Теперь перейдем к вашему последнему вопросу: как все еще возможно, что 4-х разрядная куча превзойдет двоичную кучу, учитывая приведенную здесь информацию? Я буду совершенно честен и скажу, что понятия не имею, правда ли это, но это (а), вероятно, зависит от аппаратного обеспечения, и (б) меня не удивит. Имейте в виду, что все предыдущие анализы пытались ограничить стоимость операций с кучей данных, рассматривая такие количества, как количество слоев в куче и количество выполненных перестановок. Тем не менее, это исключает множество других факторов, таких как стоимость поиска родителей и детей и месторасположение. Для первого из них обратите внимание, что в куче d-ary вы можете найти родительский узел, разделив ваш индекс на d. Для d, которые являются совершенными степенями двух, это может быть реализовано с помощью простого недорогого сдвига битов (так как n / 2k = n >> k). Для нечетных чисел или чисел, которые не имеют степеней двойки, это требует деления, которое (в некоторых архитектурах) дороже, чем сдвиг битов. Кроме того, есть влияние местности ссылки. Компьютеры в наши дни имеют огромное количество уровней кэшей в памяти, и стоимость доступа к памяти, которая находится в кэше, может быть в сотни или тысячи раз быстрее, чем стоимость доступа к памяти вне кэша. При увеличении значения d в куче d-ary в дереве становится меньше слоев, а элементы, к которым осуществляется доступ, расположены ближе друг к другу, обеспечивая лучшую локальность. Чтобы найти наилучшее место, вероятно, потребуются некоторые эксперименты, и если окажется, что d = 4 - лучший результат на вашей машине, то сделайте это!
РЕДАКТИРОВАТЬ: как указывало @moreON, для d = 4 количество слоев в куче уменьшается в два раза, а число сравнений в последующем увеличивается в два раза, что может на самом деле повысить общую производительность за счет кэшировать эффекты и более низкую общую высоту дерева. Поэтому, вероятно, это хороший кандидат, чтобы превзойти двоичную кучу.
Надеюсь это поможет!
4-арная куча в теории быстрее двоичной
поскольку 3-арная куча имеет большую стоимость в a и f(k=4)