Как оптимизировать эту структуру данных?

Question

Я недавно попросил построить структуру данных, которая поддерживает четыре операции, а именно,

1. принудительный: Добавить элемент в DS.
2. Pop: Удалите последний толкаемый элемент.
3. Find_max: Найдите максимальный элемент из сохраненных в данный момент элементов.
4. Pop_max: удалить максимальный элемент из DS.

Элементы представляют собой целые числа.

Вот решение, которое я предложил:

1. Возьмите пачку.
2. Хранить пару элементов в нем. Пара должна быть (элемент, max_so_far), где элемент является элементом этого индекса и max_so_far - это максимальный элемент, который был оценен до сих пор.
3. Нажав элемент в стек, проверьте max_so_far самого верхнего элемента стека. Если текущее число больше этого, поместите значение текущей пары max_so_far в качестве значения текущего элемента, иначе сохраните предыдущий max_so_far. Это означает, что нажатие будет просто выполнять операцию O(1).
4. Для pop просто вытащите элемент из стека. Опять же, эта операция - O(1).
5. Для Find_max верните значение max_so_far верхнего элемента в стеке. Опять же, O(1).
6. Попадание элемента max будет проходить через стек и явно удалять элемент max и отбрасывать элементы поверх него, после выделения новых значений max_so_far. Это было бы линейно.

Меня попросили улучшить его, но я не мог.

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

Answer 1

Одним из подходов было бы хранить указатели на элементы в двусвязном списке, а также в структуре данных max-heap (отсортировано по значению).

Каждый элемент сохранит свое положение в двусвязном списке, а также в макс-куче.

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

Answer 2

Одним из способов получения O (log n) -time-операций является размытие двух структур данных, в этом случае двусвязный список и очередь приоритетов (куча сопряжения является хорошим выбором).У нас есть структура узлов, такая как

struct Node { 
    Node *previous, *next; // doubly linked list 
    Node **back, *child, *sibling; // pairing heap 
    int value; 
} list_head, *heap_root; 

Теперь, чтобы нажать, мы вставляем обе структуры. Чтобы find_max, мы возвращаем значение корня кучи спаривания. Для pop или pop_max мы выходим из соответствующей структуры данных, а затем используем указатели других узлов для удаления в другой структуре данных.

Answer 3

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

Например: две карты, у которых ключи являются качеством A и качеством B, чьи значения являются общим указателем на структуру, содержащую итераторы, на обе карты и значение. Затем у вас есть log (n), чтобы найти элемент через любое качество, и стирание ~ O (logn), чтобы удалить два итератора с любой из карт.

struct hybrid { 
    struct value { 
     std::map<std::string, std::shared_ptr<value>>::iterator name_iter; 
     std::map<int, std::shared_ptr<value>>::iterator height_iter; 
     mountain value; 
    }; 
    std::map<std::string, std::shared_ptr<value>> name_map; 
    std::map<int, std::shared_ptr<value>> height_map; 

    mountain& find_by_name(std::string s) {return name_map[s]->value;} 
    mountain& find_by_height(int height h) {return height_map[s]->value;} 
    void erase_by_name(std::string s) { 
     value& v = name_map[s]; 
     name_map.erase(v.name_iter); 
     height_iter.erase(v.height_iter); //note that this invalidates the reference v 
    } 
}; 

Однако в вашем случае, вы можете сделать даже лучше, чем это O (LogN), так как вам нужно только «самые последние» и «следующий самый высокий». Чтобы быстро выполнить «поп-высоту», вам нужен быстрый способ определить следующий максимум, что означает, что его необходимо предварительно вычислять при вставке. Чтобы найти положение «высота» относительно остального, вам нужна какая-то карта. Чтобы быстро «попсовать», вам нужен быстрый способ обнаружения следующего последнего, но это тривиально рассчитано. Я бы рекомендовал создать карту или кучу узлов, где ключи - это значение для нахождения max, а значения - указатель на следующее последнее значение. Это дает вам O (logn) insert, O (1) находит самое последнее, O (1) или O (logn) находит максимальное значение (в зависимости от реализации) и стирание ~ O (logn) одним индексом.

Answer 4

Еще один способ сделать это: -

Создание макс-кучу с элементами. Таким образом, мы сможем получить/удалить max-элемент в операциях O (1). Наряду с этим мы можем поддерживать указатель на последний нажатый элемент. И насколько я знаю, удаление в кучи может быть сконструировано в O (log n).