Существует ли один тип подобной множеству структуры данных, поддерживающей объединение во время O (logn) и k-й поиск во время O (logn)? (N - размер этого набора)

Question

Существует ли один тип подобной множеству структуры данных, поддерживающей объединение во времени O (logn) и поиск k-го элемента во времени O (logn)? n - размер этого набора.

Answer 1

Если k является константой, то любая изменяемая куча сделает это, включая левые кучи , косые кучи , пары кучи и кучи Фибоначчи. Как для слияния, так и для получения первого элемента в этих структурах обычно требуется O (1) или O (lg n ) амортизированного времени, поэтому O ( k lg n ) максимум.

Обратите внимание, однако, что получение элемента k может быть разрушительным в том смысле, что первые элементы k -1 могут быть удалены из кучи.

Answer 2

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

Answer 3

Деревья пальца могут сделать это и некоторые другие операции:

http://en.wikipedia.org/wiki/Finger_tree

Может быть что-то даже лучше, если вы не ограничены чисто функциональными структурами данных (то есть, «постоянными», где под этим подразумевается не «резервное копирование на энергонезависимой памяти», а «все предыдущие« версии » структуры данных доступны даже после «добавления» дополнительных элементов ").

Answer 4

Если вы готовы принять амортизацию, вы можете достичь желаемых границ времени O (lg n) как для объединения, так и для поиска, используя двоичное дерево поиска для представления каждого набора.Для объединения двух деревьев размером m и n требуется время O (m log (n / m)), где m

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

Как указано в других ответах, вы можете использовать кучи, но для получения O (LG N) для комбинации и выбора требуется некоторая работа.