Сравнивайте с английским: нажмите на абзац — оригинал откроется в окне. Кнопка EN под абзацем показывает его прямо в тексте.
Содержание
Введение
Структура данных, функционирующая как очередь с приоритетами.
Data structure that acts as a priority queue
В информатике биномиальная куча — это структура данных, функционирующая как очередь с приоритетами. Она является примером объединяемой кучи (также называемой кучей слиянием), поскольку поддерживает объединение двух куч за логарифмическое время. Она реализована как куча, подобная бинарной куче, но использует специальную древовидную структуру, отличную от полных бинарных деревьев, используемых в бинарных кучах. Биномиальные кучи были изобретены в 1978 году Жаном Вуйлемэном.
In computer science, a binomial heap is a data structure that acts as a priority queue. It is an example of a mergeable heap (also called meldable heap), as it supports merging two heaps in logarithmic time. It is implemented as a heap similar to a binary heap but using a special tree structure that is different from the complete binary trees used by binary heaps. Binomial heaps were invented in 1978 by Jean Vuillemin.
Найти минимальный
Чтобы найти минимальный элемент кучи, найдите минимальное значение среди корней биномиальных деревьев. Это можно сделать за время O(log n), так как нужно проверить только корни деревьев. Используя указатель на биномиальное дерево, содержащее минимальный элемент, время выполнения этой операции можно сократить до O(1). Указатель необходимо обновлять при выполнении любой операции, кроме поиска минимума. Это можно сделать за время O(log n) на каждое обновление, не увеличивая общую асимптотическую сложность любой операции.
To find the minimum element of the heap, find the minimum among the roots of the binomial trees. This can be done in time, as there are just tree roots to examine. By using a pointer to the binomial tree that contains the minimum element, the time for this operation can be reduced to The pointer must be updated when performing any operation other than finding the minimum. This can be done in time per update, without raising the overall asymptotic running time of any operation.
Ключ снижения
После уменьшения ключа элемента он может оказаться меньше ключа его родителя, нарушая свойство минимальной кучи. Если это происходит, необходимо поменять элемент местами с его родителем, а возможно, и с его дедушкой, и так далее, пока свойство минимальной кучи не будет восстановлено. Поскольку высота каждого биномиального дерева не превышает , это занимает время. Однако эта операция требует, чтобы представление дерева включало указатели от каждого узла к его родителю, что несколько усложняет реализацию других операций.
After decreasing the key of an element, it may become smaller than the key of its parent, violating the minimum heap property. If this is the case, exchange the element with its parent, and possibly also with its grandparent, and so on, until the minimum heap property is no longer violated. Each binomial tree has height at most , so this takes time. However, this operation requires that the representation of the tree include pointers from each node to its parent in the tree, somewhat complicating the implementation of other operations.
Удалить
Чтобы удалить элемент из кучи, уменьшите его ключ до отрицательной бесконечности (или, что эквивалентно, до значения, меньшего любого элемента в куче), а затем удалите минимальный элемент из кучи.
To delete an element from the heap, decrease its key to negative infinity (or equivalently, to some value lower than any element in the heap) and then delete the minimum in the heap.