Структура данных с постоянными операциями времени

Question

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

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

Answer 1

Я бы предложил

1. Вы можете использовать хеш-таблицу, которая дает O(1) ожидаемое время

2. Что касается максимума, вы можете сохранить его в атрибуте и знать при каждой вставке, если максимум изменяется. С удалением это несколько сложнее, потому что если удаляется максимум, то вы должны выполнить линейный поиск, но это произойдет, только если удаляется максимум. Любой другой элемент может быть удален за O(1) ожидаемое время

Answer 2

Если бы вы могли сделать такую ​​вещь, то вы могли бы отсортировать по линейному времени: просто вставьте все свои элементы, затем выполните следующие n раз:

1. Найти максимум
2. Максимум печати
3. Удалить максимум

Следовательно, в модели вычислений, в которой вы не можете сортировать по линейному времени, вы также не можете решить свою проблему со всеми операциями за O(1) времени.

Answer 3

Да, я согласен с Irleon. Вы можете использовать хеш-таблицу для выполнения этих операций. Давайте проанализируем этот шаг за шагом:
1. Если мы возьмем массивы, временная сложность вставки будет O(1) в конце.
2. Возьмите связанные списки, и это будет O(n) из-за обхода, который вам нужно сделать.
3. Возьмите бинарные деревья поиска, и это будет O(logn), где logn - высота дерева.
4. Теперь мы можем использовать хеш-таблицы. Мы знаем, что он работает с ключами и значениями. Итак, здесь ключ будет 'number_to_be_inserted% n', где 'n' - это количество элементов, которые у нас есть.

Но по мере того, как список растет по тому же индексу, вам нужно будет просмотреть список. Так что это будет O(numbers_at_that_index).
То же самое будет в случае операции удаления.

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