我有一系列我将要处理的项目(大理性).在每种情况下,处理将包括删除集合中的最小项目,做一些工作,然后添加0-2个新项目(总是大于删除的项目).该集合将使用一个项目进行初始化,并且工作将继续进行,直到它为空.我不确定该系列可能达到的尺寸,但我希望在1M-100M范围内.我不需要找到除最小项目之外的任何项目.
我目前正计划使用一棵红黑树,可能会调整以保持指向最小项目的指针.但是我之前从未使用过,我不确定我的使用模式是否符合其特性.
1)是否存在从左+随机插入删除模式会影响性能的危险,例如通过要求比随机删除显着更高的旋转次数？或者删除和插入操作仍然是这个使用模式的O(log n)？
2)其他一些数据结构是否会给我带来更好的性能,要么是因为删除模式还是利用了我只需要找到最小项目的事实？
更新:很高兴我问,二进制堆对于这种情况显然是一个更好的解决方案,并且承诺结果很容易实现.
雨果
给定n个不同项目的列表,我如何逐步交换每次交换一对值的项目的每个排列？(我认为这是可能的,它确实应该是这样.)
我正在寻找的是一个迭代器,它产生下一对要交换的项的索引,这样如果迭代n!-1次,它将逐步通过n!列表的排列按某种顺序排列.如果再次迭代它会将列表恢复到它的起始顺序,这将是一个奖励,但它不是一个要求.如果所有对都涉及第一个(相应的是最后一个)元素作为其中一个,那么该函数只需返回一个值,这也是一个奖励.
示例: - 对于3个元素,您可以交替地将最后一个元素与第一个和第二个元素交换以循环排列,即:(abc)swap 0-2 =>(cba)1-2(cab)0-2( bac)1-2(bca)0-2(acb).
我将在C中实现,但可能会在大多数语言中解决问题.