Почему d-куча более полезна для основной памяти, чем двоичная куча?

Question

Во 2-м издании М. А. Вайса: Структуры данных и анализ алгоритмов в C , когда я узнаю о двоичной куче и d-куче , естьописание того, что когда приоритетная очередь слишком велика для полной загрузки в основную память, d-heap очень полезна.

Я думаю о поговорке, по моему мнению, когда есть N элементов, d-heap требуетбольше указателей (около Nd), но имеет меньшую высоту, а двоичная куча требует меньше указателей (около 2N), но имеет большую высоту. Так что d-куче, похоже, нужно больше места ， ведь высота не тратит память на мой взгляд. И если эти два заполняются массивом, а не указателем, им нужны одинаковые N ячеек массива. Поэтому я не могу понять:
Почему d-heap более полезна для основной памяти, чем двоичная куча ?

Answer 1

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

Предположим, что это 4-сторонняя d-куча, а у вас достаточноместо в оперативной памяти для двух двоичных узлов кучи или одного узла d-heap. Что бы вы предпочли сделать: спуститься через 10 уровней d-кучи или 20 уровней бинарной кучи? Обратите внимание, что возможность хранить два двоичных узла кучи в памяти на самом деле не будет полезна: вы только знаете, какой из них нужно поместить в оперативную память, как только посмотрите на его родительский узел. Таким образом, с двоичной кучей нужно ждать 19 раз, а с d-кучей нужно ждать 9 раз.