внедрение структуры данных

Question

У нас есть m разных продуктов (от 1 до m). тендер открыт в течение нескольких дней, в течение этих дней русский человек дает предложение о покупке (каждое предложение относится к одному продукту), В конце каждого дня продукт (формирует все продукты, которые еще не были проданы) с самым высоким предложением будет продан .

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

1. Init (м) -> инициализирует DS с т элементов без предложений
2. Bid (у, р) -> добавляет предложение с ценой p к продукту j по сложности O (1) амортизируется
3. Sell-> продает продукт с самым высоким предложением. return j (продукт, который был продан) и p (цена, в которой продукт был продан) по сложности O (log m) амортизирован.

я пытался решить вопрос с помощью fibonacce кучки:

• мы создаем новую Фибо кучу и вставить т раз (продукты с ключом у и информация нуль)

• I используйте идею уменьшения ключа в кучих флюида и переключите информацию с новым p в

• Я использую идею delete min для удаления max

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

Кто-то может помочь мне получить истинное решение?! **

Answer 1

Вы можете получить O (log M) для Bid() и O (1) для Sell(), сохранив хеш-таблицу продуктов до максимальной ставки и список товаров, отсортированный по максимальной ставке.

Для Bid() вы обновляете таблицу, если необходимо, и обновляете список с помощью бинарного поиска, если это необходимо; Для Sell() вы просто выставляете верхний элемент из списка и получаете цену с карты.