如何保持有序滑动window
How to maintain an ordered sliding window
这个问题有点跟编程语言无关。那么问题来了：
我有一个大小为 n 的滑动 window，其中包含实数。如果新插入已满，此滑动 window 会删除旧值（FIFO 方式）。时不时地（K 次），我需要特定索引中的值，索引因查询而异，window 中的有序值。所以我必须花费 O(K*nlog(n)) 对 window 和 O(1) 进行排序以获得我的价值。是否可以降低这种复杂性？在最坏的情况下（经常发生），我必须为每个新条目对 window 进行排序。
我正在考虑维护滑动值的索引 window 并维护一个排序列表。这将节省排序的复杂性，但插入或删除的复杂性是多少？另外，这样的数据结构是否已经存在？
高效选择第 ith 元素
So I have to spend O(K*nlog(n)) to sort the window and O(1) to obtain
my value. Would it be possible to reduce this complexity ?
是的。通过使用 QuickSelect 而不是完全排序，您可以将 K 选择的成本降低到 O(Kn)。如果在 O(1) 中添加 m 插入和删除的成本，则总成本为 O(m + Kn).
In the
worst case scenario (that happens frequently), I have to sort the
window for every new entry.
不，您不必这样做，因为您根本不需要（完全）排序。看上面。但是如果你确实想按排序顺序维护元素，那么你可以利用现有元素已经排序的事实，这降低了维护列表的成本，使其不超过 O(n ) 每个插入的元素，可能更少（见下文）。
维护排序索引
I was thinking of maintaining indices over the values of the sliding
window and maintain a sorted list. That would save the sorting
complexity, but what would be insertion or deletion complexity?
这要看具体情况。在所有情况下，FIFO 的插入和删除操作都可以进行 O(1)。以下是维护索引的一些更可能的替代方案：
BST指数
假设您以 red/black 树或其他某种形式的自平衡二叉搜索树的形式维护索引。那么索引的插入和删除都是 O(log n)。从这样的索引中选择 ith 元素可以在 O(i) 中完成，这不比 QuickSelect 操作未排序数据的 O(n) 差。对于 m 插入（和删除）和 K 选择，产生 O(m log n + Kn)。如果 O(m) = O(k) - 指定的最坏情况 - 即 O(Kn ) 整体。
排序，线性，运行dom-access 索引
另一方面，假设您维护支持 运行dom 访问的当前元素的排序线性索引。 运行dom 访问提供了 O(1) 的选择（或者可以做到），但是意味着维护每次插入和删除的索引成本为 O(n)，主要来自在索引中移动元素。对于 m 插入（和删除）和 K 选择，产生 O(mn + K)。如果 O(m) = O(k) - 指定的最坏情况 - 即 O(Kn ) 整体。
排序的、线性的、顺序访问的索引
另一方面，假设您维护一个需要顺序访问的当前元素的排序线性索引，例如链表。从该索引中进行选择的成本为 O(n)，向其中插入也是如此。在您的情况下可以 ar运行ge 进行 O(1) 删除，因为您无需搜索就可以知道要删除哪个节点，但是一旦您拥有 ，删除将始终与插入配对n 个元素，这对你没有真正的帮助。对于 m 插入（和删除）和 K 选择，产生 O(mn + Kn)。如果 O(m) = O(k) - 指定的最坏情况 - 即 O(Kn ) 整体。
Also,
does a data structure like this already exist ?
这里没什么新奇的。您只有第二个数据结构（或者可能是相同数据结构的第二个视图），它呈现相同数据的不同参数运行。其他数据结构可以是您已知的多种类型中的任何一种。
推荐
None 用于维护排序索引的备选方案在每次插入一个选择的表达的最坏情况下比另一个渐进地更好，或者比使用 QuickSelect 在需要时选择更好。在那种情况下，所有都是 O(Kn) 。从这个角度来看，上述任何一种方法都和另一种一样好（而且都应该是渐近改进）。
但是，由于更好的情况显然被认为是选择较少的情况，所以相关的 当 O(k) < O(m)，使用 QuickSelect 进行选择渐进地优于维护排序索引的所有变体，这些变体被认为是 。快速插入和删除在这里赢得了胜利，这就是我根据可用信息选择的方法。
如果存在 O(k) > O(m) 的情况，那么 运行dom-access 排序索引，考虑到快速选择。顺序访问索引总是一个 also-运行，但对我来说有趣的是 BST 索引在任何情况下都不是明显的赢家。
如果您在订单统计树 (https://en.wikipedia.org/wiki/Order_statistic_tree) 中维护 window 个（大小为 n）个元素，那么它将花费您 O(log n) 时间推进 window 和 O(log n) 时间找到 i-th 最大元素 window 对于任何 i。如果您必须经常进行查询，这将是一个优势。
订单统计树只是一个平衡的二叉搜索树，其中每个节点都增加了其子树的大小，这使您可以直接向下钻取到给定等级的元素。
这个问题有点跟编程语言无关。那么问题来了：
我有一个大小为 n 的滑动 window，其中包含实数。如果新插入已满，此滑动 window 会删除旧值（FIFO 方式）。时不时地（K 次），我需要特定索引中的值，索引因查询而异，window 中的有序值。所以我必须花费 O(K*nlog(n)) 对 window 和 O(1) 进行排序以获得我的价值。是否可以降低这种复杂性？在最坏的情况下（经常发生），我必须为每个新条目对 window 进行排序。
我正在考虑维护滑动值的索引 window 并维护一个排序列表。这将节省排序的复杂性，但插入或删除的复杂性是多少？另外，这样的数据结构是否已经存在？
高效选择第 ith 元素
So I have to spend O(K*nlog(n)) to sort the window and O(1) to obtain my value. Would it be possible to reduce this complexity ?
是的。通过使用 QuickSelect 而不是完全排序，您可以将 K 选择的成本降低到 O(Kn)。如果在 O(1) 中添加 m 插入和删除的成本，则总成本为 O(m + Kn).
In the worst case scenario (that happens frequently), I have to sort the window for every new entry.
不，您不必这样做，因为您根本不需要（完全）排序。看上面。但是如果你确实想按排序顺序维护元素，那么你可以利用现有元素已经排序的事实，这降低了维护列表的成本，使其不超过 O(n ) 每个插入的元素，可能更少（见下文）。
维护排序索引
I was thinking of maintaining indices over the values of the sliding window and maintain a sorted list. That would save the sorting complexity, but what would be insertion or deletion complexity?
这要看具体情况。在所有情况下，FIFO 的插入和删除操作都可以进行 O(1)。以下是维护索引的一些更可能的替代方案：
BST指数
假设您以 red/black 树或其他某种形式的自平衡二叉搜索树的形式维护索引。那么索引的插入和删除都是 O(log n)。从这样的索引中选择 ith 元素可以在 O(i) 中完成，这不比 QuickSelect 操作未排序数据的 O(n) 差。对于 m 插入（和删除）和 K 选择，产生 O(m log n + Kn)。如果 O(m) = O(k) - 指定的最坏情况 - 即 O(Kn ) 整体。
排序，线性，运行dom-access 索引
另一方面，假设您维护支持 运行dom 访问的当前元素的排序线性索引。 运行dom 访问提供了 O(1) 的选择（或者可以做到），但是意味着维护每次插入和删除的索引成本为 O(n)，主要来自在索引中移动元素。对于 m 插入（和删除）和 K 选择，产生 O(mn + K)。如果 O(m) = O(k) - 指定的最坏情况 - 即 O(Kn ) 整体。
排序的、线性的、顺序访问的索引
另一方面，假设您维护一个需要顺序访问的当前元素的排序线性索引，例如链表。从该索引中进行选择的成本为 O(n)，向其中插入也是如此。在您的情况下可以 ar运行ge 进行 O(1) 删除，因为您无需搜索就可以知道要删除哪个节点，但是一旦您拥有 ，删除将始终与插入配对n 个元素，这对你没有真正的帮助。对于 m 插入（和删除）和 K 选择，产生 O(mn + Kn)。如果 O(m) = O(k) - 指定的最坏情况 - 即 O(Kn ) 整体。
Also, does a data structure like this already exist ?
这里没什么新奇的。您只有第二个数据结构（或者可能是相同数据结构的第二个视图），它呈现相同数据的不同参数运行。其他数据结构可以是您已知的多种类型中的任何一种。
推荐
None 用于维护排序索引的备选方案在每次插入一个选择的表达的最坏情况下比另一个渐进地更好，或者比使用 QuickSelect 在需要时选择更好。在那种情况下，所有都是 O(Kn) 。从这个角度来看，上述任何一种方法都和另一种一样好（而且都应该是渐近改进）。
但是，由于更好的情况显然被认为是选择较少的情况，所以相关的 当 O(k) < O(m)，使用 QuickSelect 进行选择渐进地优于维护排序索引的所有变体，这些变体被认为是 。快速插入和删除在这里赢得了胜利，这就是我根据可用信息选择的方法。
如果存在 O(k) > O(m) 的情况，那么 运行dom-access 排序索引，考虑到快速选择。顺序访问索引总是一个 also-运行，但对我来说有趣的是 BST 索引在任何情况下都不是明显的赢家。
如果您在订单统计树 (https://en.wikipedia.org/wiki/Order_statistic_tree) 中维护 window 个（大小为 n）个元素，那么它将花费您 O(log n) 时间推进 window 和 O(log n) 时间找到 i-th 最大元素 window 对于任何 i。如果您必须经常进行查询，这将是一个优势。
订单统计树只是一个平衡的二叉搜索树，其中每个节点都增加了其子树的大小，这使您可以直接向下钻取到给定等级的元素。