Как создать очередь событий в порядке по дате

Question

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

3446 --- 9493 ---15969 --- 48381

где число может быть в миллисекундах или еще много чего.

Как я могу вставить событие между событиями 9493 и 15969?

Я мог быиспользовать бинарный поиск, чтобы найти события в очереди с требуемым временем, но есть ли более простой способ?

Answer 1

То, что вы ищете, называется приоритетной очередью:

https://en.wikipedia.org/wiki/Priority_queue

Типичным способом реализации является использование кучи;Вы получаете O(log n) время вставки и O(log n) время удаления (для удаления элемента с наивысшим приоритетом из очереди). Проверьте на странице Википедии список других потенциальных структур данных, некоторые из которых лучше амортизируются.