Я на самом деле не построил это, но я сделал довольно обширный анализ этой идеи, и похоже, что она должна работать. Я называю это очередью очередей. Причина, по которой я никогда не строил ее, - это то, что проект, который я строю для нее, был отменен, прежде чем мне понадобилась очередь.
Во-первых, я решил, что «простой элемент» вместо этого будет очередью приоритетов, которая содержит один элемент. Отсутствие управления двумя различными типами элементов упростило дизайн, и анализ показал, что он не должен влиять на производительность каким-либо значительным образом.
Поскольку приоритет вспомогательной очереди может меняться всякий раз, когда новый элемент добавляется или элемент удаляется из него, я решил использовать Pairing heap для основной очереди и подклассов. Сопряженная куча работает лучше, чем двоичная куча, когда вам приходится делать много приоритетных изменений. Проблема с бинарной кучей заключается в том, что если вы хотите изменить приоритет элемента, вам нужно сначала найти элемент. В двоичной куче это операция O (n). В куче спаривания амортизационная стоимость изменения приоритета равна O (log n), поскольку у вас уже есть ссылка на узел.
Итак, идея состоит в том, что если вы добавляете новую подсечку, вы просто добавляете ее в основную очередь, и она будет вставлена в нужное место. Если вы обновляете подчиненную очередь, вы добавляете или удаляете элемент (который является O (log n) в подсете), а затем корректируйте положение поддиректа в основной очереди (что является O (log n) в главной очереди).
Весь мой анализ сказал, что это должно работать достаточно хорошо, хотя я все еще не уверен, насколько хорошо он будет работать с несколькими потоками. I думаю У меня есть хорошая идея, как синхронизировать доступ и не блокировать всю очередь для каждой вставки и удаления, за исключением очень короткого времени. Наверное, я выясню, смогу ли я когда-либо его построить. Это может быть может быть можно создать блокирующую кучу спаривания.
Я выбрал парную кучу из-за ее лучшей производительности при переупорядочивании ключей, а также потому, что ее намного проще реализовать, чем куча Фибоначчи или многих других, и хотя ее асимптотическая производительность медленнее, чем куча Фибоначчи, мировая производительность намного, намного лучше. Единственным недостатком для меня является то, что куча спаривания будет занимать больше памяти, чем эквивалентная двоичная куча. Это старый компромисс между временем и пространством.
Другим вариантом является реализация очереди приоритетов skip list, которая также имеет производительность O (log n) для вставки и изменения приоритета. И я видел блокирующие параллельные реализации списка пропуска.Внедрение эффективного списка пропусков в C не сложно, поскольку он отлично обрабатывает переменные размеры записей. В C# и других языках, которые не позволяют создавать различные структуры длины, список пропусков может быть реальным всплеском памяти.
Как я уже сказал, я никогда не строил эту вещь, но все мои исследования и примечания по дизайну говорят мне о том, что ее можно легко построить и выполнить достаточно хорошо.