251
правка
Изменения
м
Красивая табличка
Рассмотрим операции, которые можно производить с биномиальной кучей. Время работы указано в таблице:
{| class="wikitable" style="width:10cm" border=1|+|-align="1center" bgcolor=#EEEEFF! Операция || Время работы |-align="center"bgcolor=#FFFFFF |<math>\mathrm {insert}</math> ||<tex>O(\log n)</tex> |-align="center" bgcolor=#FFFFFF |<math>\mathrm {getMinimum}</math> ||<tex>O(\log n)</tex> |-align="center" bgcolor=#FFFFFF ||<math>\mathrm {extractMin}</math> ||<tex>\Theta(\log n)</tex> |-align="center" bgcolor=#FFFFFF |<math>\mathrm {merge}</math> ||<tex>\Omega(\log n)</tex> |-align="center" bgcolor=#FFFFFF |<math>\mathrm {decreaseKey}</math> ||<tex>\Theta(\log n)</tex> |-align="center" bgcolor=#FFFFFF |<math>\mathrm {delete}</math> ||<tex>\Theta(\log n)</tex> |}
Обозначим нашу кучу за <tex>H</tex>. То пусть <tex>H.head</tex> {{---}} указатель на корень биномиального дерева минимального порядка этой кучи. Изначально <tex>H.head = null</tex>, то есть куча не содержит элементов.
