Почему узел в структуре данных кучи во многих типах имеет только двух дочерних элементов?

Question

Из вики

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

Я не могу понять, почему во многих типах у узла в куче самое большее только два потомка?Почему трое детей или четверо детей и так далее не распространены?Благодаря ~

Answer 1

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

Структуры данных, используемые для двоичных куч, могут использоваться с различным числом дочерних элементов на узел,Обычные операции в x -ной куче по-прежнему занимают O (log N) время, если мы считаем x постоянным.Однако для выбора лучшего x мы должны позволить ему варьироваться, и в этом случае обычные операции занимают O (x * log N / log x) время.

Чтобы определить наиболее эффективное число дочерних элементов на узел, мы можем выбрать x , чтобы минимизировать коэффициент x / log x .

Если вы планируете, что выможно увидеть, что наилучшее число дочерних элементов на узел фактически равно 3 (минимальное значение при x = e, но нам требуется целое число):

... но разница между 2 и 3 несущественна, и код проще, используя 2 дочерних узла на узел, так что это обычная практика.