Вопрос структуры данных

Question

Этот вопрос из экзамена, который я сдал, и я не смог его решить, и хотел посмотреть, каков ответ (это не домашняя работа, поскольку она не поможет мне ни в чем, кроме знаний).

Нам нужно создать структуру данных для элементов, ключи которых являются действительными числами.
Структура данных должна иметь следующие функции:
Build (S, массив): строит структуру данных S с n элементами в O (n)
Вставить (S, k) и Удалить (S, x) в O (lgn) (k - элемент, x - указатель на него в структуре данных)
Delete-Minimal-Positive (S): Удалить элемент с минимальным положительным ключом
Режим (S): возвращает ключ, наиболее часто встречающийся в S, в O (1)

Теперь построение в O (n) обычно означает, что следует использовать кучу, но это не позволяет найти частоты. Я не мог найти способ сделать это так. Лучшее, что я могу придумать, - это создать красно-черное дерево (O (nlgn)), которое будет использоваться для построения кучи частот.

Мне не терпится узнать ответ ...

Спасибо!

Answer 1

Используя только модель сравнения , не существует решения для этой проблемы.

В проблеме разграничения элементов есть доказуемое Omega (nlogn) нижние границы.Эта проблема (отличимости элементов) в основном заключается в определении того, различны ли все элементы массива.

Если бы было решение вашей проблемы, то мы могли бы ответить на проблему отличимости элементов в O (n)время (найдите наиболее частый элемент за время O (n) и посмотрите, есть ли более одного экземпляра этого элемента, опять же за время O (n)).

Итак, я предлагаю вам спросить своего профессорадля вычислительной модели.

Answer 2

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

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

Предполагая, что хеш-таблица представляет собой операцию O (1), у вас есть стандартная хеш-таблица heap + O (1), и вы получаете все вышеперечисленные операции в установленные сроки. В частности, вы получаете «режим», читая корневой элемент кучи.

Answer 3

Для частот:
Каждая запись двунаправленно связана с собственными частотами / счетчиками (используйте хэш-таблицу)
Частоты находятся в связанном списке.
Необходимо переместить частоту вверх / вниз по связанному списку, (удаление вставляющего элемента), но для максимальной разницы 1.

Частоты, таким образом, связаны с указателем элемента частоты +1 и -1.

(есть исключения, но они могут быть обработаны)

Answer 4

Я думаю, что следующее решение будет приемлемым.Он основан на двух структурах данных:

1. Красно-черное дерево
2. Двоичная куча

Двоичная куча содержит кортеж, который содержит (значение элемента, частотуэлемент), куча построена на частотах, так что это дает нам возможность найти режим в O (1).

Красно-черное дерево содержит кортеж, который содержит (значение элемента, указатель на то же значение элемента в куче)

Когда вам нужно вставить новый элемент, вы попытаетесь найти элемент (он занимает O(log n)), если поиск был успешным, перейдите к указателю из элемента, найденного в RB-дереве, увеличьте частоту и восстановите кучу (также O (log n)).Если поиск не нашел такого элемента, чем вставить его в RB-дерево (O (log n)) и сложить со значением = (element, 1) (также O (1)), установите указатель в RB-дереве на новыйэлемент в куче.

Первоначальное построение займет O (n), потому что построение обеих структур из набора элементов n требует O (n).

Извините, если я что-то пропустил.