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

'''Отсортированный список ключей''': отсортированный список содержит большинство ключей в структуре данных, в том числе минимальный ключ, и называется базовым списком. Этот список разбит на базовые сегменты, каждый из которых содержит ©((log n)2) ключей. Ключи в каждом сегменте поддерживаются в виде атомарной кучи, так что если становится известно, что новое обновление должно быть применено к конкретному сегменту, оно может быть применено за время O(1). Если базовый сегмент становится слишком большим или слишком маленьким, он разбивается на две части либо объединяется со смежным сегментом.

'''Буферы обновления''': базовые сегменты отделяются друг от друга базовыми разделителями, из которых O(log n) выбираются в качестве верхних разделителей, так что количество ключей в базовом списке под i-м верхним разделителем (i > 0) составляет & (4'(log и)2). Эти разделители располагаются а атомарной куче. По мере изменений базового списка верхние разделители перемещаются по необходимости с тем, чтобы сохранить их экспоненциальное распределение.

С каждым верхним разделителем si, i > 1, ассоциированы три буфера: входной буфер, буфер сортировки и буфер слияния, каждый емкостью в 4i ключа. Верхний разделитель si работает по циклу, состоящему из 4i шагов. В начале цикла входной буфер пуст, буфер сортировки содержит не более 4i обновлений, а буфер слияния – отсортированный список из не более чем 4i обновлений. На каждом этапе можно принять обновление во входной буфер, потратить O(4i) = S(n) времени на буфер сортировки и O(1) времени на слияние отсортированного списка в буфере слияния, в то время как O(4i) базовых разделителя находятся в интервале [s,_2,s;+i) (предполагая s0 = 0, s-i = — oo), и сканирование на наличие нового si среди них. Данная реализация гарантирует, что все ключи в буферах разделителя si находятся в интервале [s,_2; si+1). Таким образом, после 4i таких шагов цикла отсортированный список корректно слит с базовым списком, найдено новое значение si и создан новый отсортированный список. Затем буфер сортировки принимает на себя роль буфера слияния, входной буфер становится буфером сортировки, а пустой буфер слияния становится новым входным буфером.

'''Обработка обновлений''': при получении нового ключа обновления k (вставка или удаление) атомарная куча с верхними разделителями позволяет за время O(1) найти разделитель si, такой, что k 2 [s,_i,s,). Если к 2 [S0;S1), его положение определяется между O(1) базовыми разделителями под s1, и соответствующий базовый сегмент обновляется за время O(1) с использованием атомарной кучи над ключами этого сегмента. Если k 2 [s,-_i, si) для некоторого i > 1, обновление размещается во входном буфере si, выполняя один шаг цикла si за время S(n) + O(1). Кроме того, во время каждого обновления выбирается еще один разделитель sr в порядке круговой очереди, и фрагмент 1/log n шага цикла sr выполняется за время O(1). Работа с sr гарантирует, что после каждых O((log n)2) обновлений выполняется некоторое перемещение каждого верхнего разделителя.