Эквивалентность между очередями с приоритетами и сортировкой: различия между версиями

С каждым верхним разделителем <math>s_i</math>, i > 1, ассоциированы три буфера: ''входной буфер'', ''буфер сортировки'' и ''буфер слияния'', каждый емкостью в <math>4^i</math> ключа. Верхний разделитель <math>s_i</math> работает по циклу, состоящему из <math>4^i</math> шагов. В начале цикла входной буфер пуст, буфер сортировки содержит не более <math>4^i</math> обновлений, а буфер слияния – отсортированный список из не более чем <math>4^i</math> обновлений. На каждом этапе можно принять обновление во входной буфер, потратить <math>O(4^i) = S(n)</math> времени на буфер сортировки и O(1) времени на слияние отсортированного списка в буфере слияния, в то время как <math>O(4^i)</math> базовых разделителя находятся в интервале <math>[s_{i - 2}, s_{i + 1})</math> (предполагая <math>s_0 = 0, s_{-1} = - \infty)</math>, и сканирование на наличие нового <math>s_i</math> среди них. Данная реализация гарантирует, что все ключи в буферах разделителя <math>s_i</math> находятся в интервале <math>[s_{i - 2}, s_{i + 1})</math>. Таким образом, после <math>4^i</math> таких шагов цикла отсортированный список корректно слит с базовым списком, найдено новое значение <math>s_i</math> и создан новый отсортированный список. Затем буфер сортировки принимает на себя роль буфера слияния, входной буфер становится буфером сортировки, а пустой буфер слияния становится новым входным буфером.

'''Обработка обновлений''': при получении нового ключа обновления k (вставка или удаление) атомарная куча с верхними разделителями позволяет за время O(1) найти разделитель <math>s_i</math>, такой, что <math>k \in [s_{i - 1}, s_i)</math>. Если <math>k \in [s_0, s_1)</math>, его положение определяется между O(1) базовыми разделителями под s1, и соответствующий базовый сегмент обновляется за время O(1) с использованием атомарной кучи над ключами этого сегмента. Если <math>k \in [s_{i - 1}, s_i)</math> для некоторого i > 1, обновление размещается во входном буфере <math>s_i</math>, выполняя один шаг цикла <math>s_i</math> за время S(n) + O(1). Кроме того, во время каждого обновления выбирается еще один разделитель <math>s_r</math> в порядке круговой очереди, и фрагмент (1/log n) шага цикла <math>s_r</math> выполняется за время O(1). Работа с <math>s_r</math> гарантирует, что после каждых <math>O((log \; n)^2)</math> обновлений выполняется некоторое перемещение каждого верхнего разделителя.