使用o(klogk)中的稀疏表对范围中的k-最小元素进行排序。

这个想法非常类似于如何从 Cartesian Tree 在O(klogk)中排序。

解决方法是用一分钟 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最小的节点中,它是第一个。 现在,通过类似的参数,下一个最小的元素必须是该节点的两个子元素之一。 下一个最小的将是根的另一个子节点,或者是我们刚取的节点的两个子节点中的一个子节点,依此类推。

SOW我们如何利用这个来解决我们的问题?

我们可以将数组中的任何特定范围视为笛卡尔树,方法是说范围中的最小值是根(我们可以使用稀疏表在O(1)中找到它),它的左子级是根和最左索引之间的最小值(除非最小值在最左索引中,在这种情况下它将为空),并且左子节点的右子节点是左子节点和根节点之间的最小值,我们可以继续这样,在不实际构建笛卡尔树的情况下获取每个节点的子节点。

因此,我们可以对笛卡尔树使用相同的算法,但不是从笛卡尔树插入堆节点,而是插入节点的子树范围,堆的键将是该范围的rmq(范围内的最小值,我们可以在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