Ну-ка, дайте подумать. Если Вы добавляете приоритет, то Вам надо сохранять двойной порядок: по приоритету, затем - по времени. Если Вы захотите все это в один контейнер совать, то у Вас вставка будет в лучшем случае О(logN). Плохо. Если приоритет временно не нужен, то FIFO дает О(1). Иначе можно создать по одному отдельной очереди на каждое значение приоритета и внутри очередей изпользовать какой-нибудь простой (кольцевой? deque?) буффер с О(1) вставкой. Тогда добавление будет О(m), где m - количество приоритетов, которое Вы сейчас используете. Хмммм...
![[personal profile]](https://www.dreamwidth.org/img/silk/identity/user.png)
timeasmymeasure
no subject
Date: 2003-05-29 12:56 pm (UTC)Ну-ка, дайте подумать. Если Вы добавляете приоритет, то Вам надо сохранять двойной порядок: по приоритету, затем - по времени. Если Вы захотите все это в один контейнер совать, то у Вас вставка будет в лучшем случае О(logN). Плохо. Если приоритет временно не нужен, то FIFO дает О(1). Иначе можно создать по одному отдельной очереди на каждое значение приоритета и внутри очередей изпользовать какой-нибудь простой (кольцевой? deque?) буффер с О(1) вставкой. Тогда добавление будет О(m), где m - количество приоритетов, которое Вы сейчас используете.
Хмммм...