data-structures - 如何维护有序的滑动窗口

Question

这个问题与编程语言无关。那么问题来了:

我有一个大小为 n 的滑动窗口，其中包含实数。如果该滑动窗口已满，则每次新插入时都会删除旧值(先进先出方式)。时不时地(K次)，我需要特定索引中的值，每个查询的索引都不同，该窗口内的有序值。所以我必须花费 O(K*nlog(n)) 对窗口进行排序，并花费 O(1) 来获取我的值。有可能降低这种复杂性吗？在最坏的情况下(经常发生)，我必须对每个新条目的窗口进行排序。

我正在考虑维护滑动窗口值的索引并维护排序列表。这会节省排序的复杂性，但是插入或删除的复杂性是多少呢？另外，这样的数据结构是否已经存在？

Answer 1

如果您在订单统计树 ( https://en.wikipedia.org/wiki/Order_statistic_tree ) 中维护窗口(大小为 n)个元素，那么您将花费 O(log n) 时间来推进窗口，并且 >O(log n) 时间查找窗口中任意 i 的第 i 个最大元素。如果您必须经常进行查询，这将非常有利。

顺序统计树只是一个平衡的二叉搜索树，其中每个节点都根据其子树的大小进行扩展，这使您可以直接向下钻取给定排名的元素。