插入排序列表，在固定的时间 [英] Insertion into a sorted list, in constant time

问题描述

我有一个整数的排序名单，我想插入此列表中的任何元素，在一定的时间。我被允许做一些pre-处理，只要它让我跑这个操作在固定时间内（即，无论多少次，我的pre-处理后重复此操作，它应该在固定时间内运行）。

如何才能做到这一点？

编辑：我能想到的一对夫妇的更多的约束，使其少了几分暧昧，有点更具挑战性来解决 -

1. 列表需要保持在有序插入后（S）
2. 或者，列出需要以某种方式支持最大/最小操作都在固定时间后插入（S）。

解决方案

您可以把整数变成基数树，对待作为整数位串。随着2基数和32位整数的列表，你将有一个树的最大深度为32，这是你的不变因素的固定时间的插入（你通常不会做这样的事，因为为常数因子基数树很可能会比平衡二叉树的日志系数较大，再加上所有的位摆弄你需要做的基数树将是昂贵的）

I have a sorted list of integers, and I wish to insert into this list any element, in constant time. I'm allowed to do some pre-processing, as long as it will let me run this operation in constant time (i.e., no matter how many times I repeat this operation after the pre-processing, it should run in constant time).

How can this be done?

Edit : I can think of a couple of more constraints to make it a bit less ambiguous, and a bit more challenging to solve -

1. list needs to be maintained in sorted order post-insertion(s)
2. Or, list needs to somehow support max/min operations in constant time post insertion(s).

解决方案

You can put the integers into a radix tree, treating the integers as bit strings. With a radix of 2 and a list of 32-bit integers you'll have a maximum tree depth of 32, which is your constant factor for constant-time insertion (you wouldn't ordinarily do something like this because the constant factor for the radix tree is probably going to be larger than the log factor of a balanced binary tree, plus all of the bit twiddling you'll need to do in for the radix tree is going to be costly)

这篇关于插入排序列表，在固定的时间的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！