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

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

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

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

Я умираю, чтобы узнать ответ...

Спасибо!

Ответ 1

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

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

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

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

Ответ 2

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

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

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

Ответ 3

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

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

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

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

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

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

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

Ответ 4

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

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

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