Разделенная биномиальная куча

Question

Я пытаюсь придумать идею сделать новую операцию Split, которая по заданной биномиальной куче .

Вопрос в том, как разбить биномиальную кучу (размер n) набиноминальная куча размера k (k

Answer 1

Вы можете найти kth самый большой элемент набора за O(n) время с помощью алгоритма медианы медиан. Источник .

Когда у вас есть это значение, вы можете прочитать все значения из исходной кучи (не нужно извлекать, их порядок не имеет значения при чтении, только при записи вновые массивы. Это дает дополнительное преимущество, заключающееся в том, что они не мешают исходной куче (Yay.) и помещаются в большую или маленькую кучу, в зависимости от их отношения к значению kth.Каждое извлечение O(1) и происходит n раз.Каждая вставка имеет значение O(lg n) и встречается n раз.

Total running time: n +  n  + n lg n = O(n lg n)
                    |    |       |
             selection   |    inserts
                     extraction

Answer 2

Поскольку деревья биномиальной кучи могут быть представлены в виде двоичных цифр n, вы можете разделить кучу в O (log (n)), просто выполнив двоичное длинное вычитание между n и k, где каждый раз, когда вам нужно «одолжить» "цифра, которую вы разделили пополам одно дерево. это похоже на слияние биномиальных деревьев, но с использованием двоичного длинного вычитания вместо сложения на деревьях.

Answer 3

Вы можете сделать это в k * log (n), просто удалив k элементов из исходной кучи и переместив их в новую другую кучу. (это при условии, что куча является минимальной кучей, если это максимальная куча, то это можно сделать таким же образом в (n-k) log (n))