数据结构创建（PQ链表合并？）
因此，我需要找到一种适合这种情况的数据结构，我将对此进行描述： 这不是我的问题，但更简洁地解释了我需要的数据结构方面： 我有一支由排组成的军队。每个排都有一定数量的人员和一个军衔编号（越高越好）。如果敌人要攻击我的军队，他们会杀死我军队的一些力量，从最弱的排开始，逐渐增加，需要（排级）的力量来杀死排中的每个士兵。
我可以通过从排的优先队列中查看和弹出元素（按等级编号排序）来轻松模拟攻击我的敌人，但这不是我需要做的。我需要的是能够允许敌人查看他们攻击我时他们会杀死的所有士兵，而无需实际攻击，因此无需实际删除我的优先级队列中的元素（如果我将其实现为 pq）。
旁注：Java 的 PriorityQueue.Iterator() 以随机顺序打印元素，我知道迭代器就是我所需要的，仅供参考。
问题是，如果我将其实现为 pq，我只能看到顶部元素，因此我必须将排弹出，就好像它们即将死亡一样，然后在计算出攻击想法后将它们推回原处。我也可以将其实现为链表或数组，但插入时间太长。最终我很想使用优先级队列，我只需要能够查看 pq 中的第（选择一个索引）元素，或者让 pq 中的每个对象都有一个指向 pq 中下一个对象的指针，例如一个链接列表。
这种想法是否可以在java的PriorityQueue中使用pq（如链表）来维护指针？它是否在我不知道的 PriorityQueue 中的某个地方为我实现了？索引的事情实现了吗？我可以使用另一种数据结构来更好地服务于我的目的吗？我从Java的PriorityQueue中找到源代码并在我的机器上重写它以像链表一样维护这些指针是否现实？ 任何想法都非常受欢迎，但不确定我想走哪条路。
So I need to find a data structure for this situation that I'll describe:
This is not my problem but explains the data structure aspect i need more succinctly:
I have an army made up of platoons. Every platoon has a number of men and a rank number(highest being better). If an enemy were to attack my army, they would kill some POWER of my army, starting from the weakest platoon and working up, where it takes (platoon rank) amount of power to kill every soldier from a platoon.
I could easily simulate enemies attacking me by peeking and popping elements from my priority queue of platoons, ordered by rank number, but that is not what I need to do. What i need is to be able to allow enemies to view all the soldiers they would kill if they attacked me, without actually attacking, so without actually deleting elements from my priorityqueue(if i implemented it as a pq).
Sidenote: Java's PriorityQueue.Iterator() prints elements in a random order, I know an iterator is all I need, just fyi.
The problem is, if I implemented this as a pq, I can only see the top element, so I would have to pop platoons off as if they were dying and then push them back on when the thought of the attack has been calculated. I could also implement this as a linked list or array, but insertion takes too long. Ultimately I would love to use a priority queue I just need the ability to view either the (pick an index)'th element from the pq, or to have every object in the pq have a pointer to the next object in the pq, like a linked list.
Is this thought about maintaining pointers with a pq like a linked list possible within java's PriorityQueue? Is it implemented for me somewhere in PriorityQueue that I dont know about? is the index thing implemented? is there another data structure I can use that can better serve my purpose? Is it realistic for me to find the source code from Java's PriorityQueue and rewrite it on my machine to maintain these pointers like a linked list?
Any ideas are very welcome, not really sure which path I want to take on this one.
如果你对这篇内容有疑问，欢迎到本站社区发帖提问 参与讨论，获取更多帮助，或者扫码二维码加入 Web 技术交流群。
绑定邮箱获取回复消息
由于您还没有绑定你的真实邮箱，如果其他用户或者作者回复了您的评论，将不能在第一时间通知您！
发布评论
评论（1）
你可以做的一件事是增强二叉搜索树。这将允许有效访问第 n 个最小元素，同时仍然保持元素有序。您还可以使用线程二叉搜索树。这将允许您在恒定时间内从一个元素步进到下一个较大的元素，这比普通二叉树更快。不过，这两种数据结构都比堆慢。
One thing you could do is an augmented binary search tree. That would allow efficient access to the nth smallest element while still keeping the elements ordered. You could also use a threaded binary search tree. That would allow you to step from one element to the next larger one in constant time, which is faster than in a normal binary tree. Both of these data structures are slower than a heap, though.