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

Question

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

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

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

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

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

Answer 1

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

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

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