Идея очень похожа на то, как получить k-мельчайшие элементы из декартового дерева , отсортированного по O (klogk).
Решением для этого является использование min Binary Heap и вставляем корень дерева, а затем k раз мы удаляем элемент min из кучи и вставляем его сыновей в дерево.
Псевдокод для задачи о декартовом дереве:
minValues(k, root):
arr = Array[0 . . . k - 1]
heap = emptyMinHeap()
heap.insert(root)
for(i = 0 . . . k - 1):
node <- heap.pop()
arr[i] <- node.key
if node has left son: heap.insert(node.left)
if node has right son: heap.insert(node.right)
return arr
Причина, по которой это работает, заключается в том, что дочерние элементы узла в декартовом дереве не меньше, чем сам узел.Итак, мы знаем, что самый маленький узел находится в корне, и, следовательно, это первый из K самых маленьких.Теперь, по аналогичному аргументу, следующий наименьший элемент должен быть одним из двух дочерних элементов этого узла.Следующим наименьшим будет либо другой потомок корня, либо один из двух потомков узла, который мы только что взяли, и так далее ...
Соу, как мы можем использовать это для решениянаша проблема?
Мы можем «обработать» любой конкретный диапазон в массиве как декартово дерево, сказав, что минимальное значение в диапазоне является корнем (мы можем найти его в O (1), используяразреженной таблицы), и его левый потомок является значением min между корнем и самым левым индексом (если только значение min не находится в самом левом индексе и в этом случае оно будет равно NULL), а правый потомок левого дочернего элемента являетсямин между левым потомком и корнем, и мы можем продолжать таким образом, чтобы получить дочерние элементы каждого узла без фактического построения декартового дерева.
Таким образом, мы можем использовать тот же алгоритм для декартового дерева, но вместо вставки в узлы кучииз декартового дерева мы вставляем диапазон поддерева узла, и ключом кучи будет RMQ для этого диапазона (минимальное значение в строкеe, который мы можем найти в O (1)).
Например: если у нас есть это декартово дерево: И мы хотим вставить узел со значением 3, которое мы вставляемв кучу вместо диапазона:
0,2
И если мы хотим вставить узел со значением 10, мы вставляем в кучу:
5,9
И если мы хотим вставить корень, мы вставляем в кучу:
0, 10
И так далее ...
Поскольку поиск значенияузла (минимум в диапазоне) принимает O (1), сложность этого алгоритма будет одинаковой (O (klogk)).
Псевдокод:
//assuming our static array is called: St
K_MinValuesInRange(k, left, right, SparseTable):
arr = Array[0 . . . k - 1]
/*key of node in the heap is determined
by St[SparseTable.RMQ(node.left, node.right)]
which takes O(1) to calculate*/
heap = emptyMinHeap()
heap.insert(left, right)
for(i = 0 . . . k - 1):
node <- heap.pop()
min_pos <- SparseTable.RMQ(node.left, node.right)
arr[i] <- St[min_pos]
/* if node has left son: insert left son*/
if node.left < min_pos: heap.insert(node.left, min_pos - 1)
/* if node has right son: insert right son*/
if node.right > min_pos: heap.insert(min_pos + 1, node.right)
return arr