数据结构创建(PQ链表合并？)

Question

因此，我需要为这种情况找到一个数据结构，我将这样描述:这不是我的问题，但更简洁地解释了我需要的数据结构方面:我有一支由排组成的军队。每个排都有一定数量的人和军衔号(越高越好)。如果敌人攻击我的军队，他们会杀死我的军队的一些力量，从最弱的排开始，然后逐步增加，这样(排级)就可以杀死一个排中的每个士兵。

我可以很容易地模拟敌人攻击我，通过偷看和弹出我的优先排中的元素，按排号排序，但这不是我需要做的。我需要的是能够允许敌人查看他们在攻击我时会杀死的所有士兵，而不是真正的攻击，所以不会从我的优先级队列中删除元素(如果我将其实现为pq)。

旁注:Java的PriorityQueue.Iterator()以随机的顺序打印元素，我知道我只需要一个迭代器，仅供参考。

问题是，如果我将其作为pq实现，我只能看到顶部的元素，所以我将不得不弹出排，就好像他们快要死了一样，然后当攻击的想法被计算出来时，再把他们推回去。我也可以将其实现为链表或数组，但插入时间太长。最终，我喜欢使用优先级队列，我只需要能够查看pq中的第(pick an Index)个元素，或者让pq中的每个对象都有一个指向pq中下一个对象的指针，比如链表。

在java的PriorityQueue中，是否可以使用类似于链表的pq来维护指针？它是在我不知道的PriorityQueue中为我实现的吗？索引的事情实现了吗？有没有其他的数据结构可以更好地服务于我的目的？对我来说，从Java的PriorityQueue中找到源代码并在我的机器上重写它来像维护链表一样维护这些指针是现实的吗？任何想法都是非常受欢迎的，我真的不确定我想走哪条路。

Answer 1

您可以做的一件事是augmented binary search tree。这将允许有效地访问第n个最小的元素，同时仍然保持元素的排序。您也可以使用threaded binary search tree。这将允许您在恒定的时间内从一个元素步进到下一个更大的元素，这比普通的二叉树更快。不过，这两种数据结构都比堆慢。