Обобщение стек find-min / find-max в статистику произвольного порядка?
В этот более ранний вопрос OP запросил структуру данных, аналогичную стеку, поддерживающему следующие операции за O (1) раз каждая:
- Push, который добавляет новый элемент поверх стека,
- Pop, который удаляет верхний элемент из стека,
- Find-Max, который возвращает (но не удаляет) самый большой элемент стека, и
- Find- Min, который возвращает (но не удаляет) наименьший элемент стека.
Несколько минут назад я обнаружил этот связанный вопрос с просьбой пояснить аналогичную структуру данных, которая вместо того, чтобы разрешить max и min для запроса, позволяет запрашивать средний элемент стека. Эти две структуры данных кажутся частным случаем более общей структуры данных, поддерживающей следующие операции:
- Push, который подталкивает элемент к вершине стека,
- Pop, который выталкивает вершину стека, и
- ] Find-Kth, который для фиксированного k, определенного при создании структуры , возвращает k-й по величине элемент стека.
Можно поддерживать все эти операции, сохраняя стек и сбалансированное двоичное дерево поиска, содержащее верхние k элементов, что позволило бы всем этим операциям выполняться за время O (log k). У меня такой вопрос: можно ли реализовать вышеуказанную структуру данных быстрее, чем эта? То есть можем ли мы получить O (1) для всех трех операций? Или, возможно, O (1) для push и pop и O (log k) для поиска статистики заказа?