Может ли карта и минимальная куча, используемые вместе, дать лучшее амортизированное время по сравнению с самим собой?
Предположим, у меня есть проект, в котором мне нужно отслеживать несколько элементов.Эти элементы имеют срок действия и уникальный идентификатор:
class Item {
ID uid;
Time expiration;
};
. В этом примере и Time, и ID являются примитивными целочисленными типами данных.Мне нужно иметь возможность быстрого доступа к элементу по идентификатору, а также мне нужно найти минимальный срок действия всех элементов.
Кроме того, я буду делать многочисленные вставки и удаления.* Используя карту, я получу амортизированное время поиска O (log n).(Да, я предоставлю функцию сравнения для этого.) Но нахождение минимального значения O (n).
Если я использую минимальную кучу, мое время поиска по id будет O (n), но нахождение минимального срока действия равно O (1).
В обоих случаях вставка равна O (log n).Для этой программы удаление будет происходить только для минимального элемента.
Или я мог бы использовать оба.Карта и минимальная куча, которые отслеживают одни и те же объекты.
Учитывая эту настройку, было бы полезно использовать как мини-кучу, так и карту, чтобы избежать сложности O (n)?