Я думаю, что вы можете решить эту проблему, используя B-дерево с небольшими изменениями.
B-деревья специально предназначены для хранения отсортированных элементов на диске таким образом, чтобы минимизировать количество дисков.читает необходимо найти любой элемент.Поскольку они хранят свои элементы в отсортированном порядке, вы можете использовать их в качестве очередей с приоритетами, выполняя вставки как обычно и находя минимальный элемент, беря самый левый элемент в дереве (то есть первый элемент самого левого конечного узла).
В B-дереве порядка d вы можете найти минимальный элемент, используя O (log d n) чтения и записи диска, где n - общее количество элементов.Для вставки и удаления также потребуется только O (log d n) чтения и записи на диск.
Однако вы можете значительно ускорить это, сохранив указатель на самый левый конечный узел в B-tree.Этот узел будет хранить ключ минимума плюс другие ключи, близкие к минимуму.Если у вас есть этот указатель, вы можете найти минимальное значение при чтении с одного диска, взяв первый элемент в узле.Это также ускоряет операцию извлечения: вы можете удалить ключ непосредственно из этого узла без необходимости его поиска.Для выполнения этой операции могут потребоваться некоторые операции перебалансировки B-дерева, хотя вы можете показать, что эти операции происходят так редко, что амортизированная операция по удалению равна только O (1).
Другими словами, использование B-дерева с указателем на крайний левый лист имеет следующие временные сложности с точки зрения чтения и записи на диск:
- find-min: O (1)
- вставка: O (log d n)
- выдержка-мин: O (1) Амортизированный
Надеюсь, это поможет!