Results 1 to 3 of 3
  1. #1
    leeple is offline Member
    Join Date
    Feb 2011
    Posts
    1
    Rep Power
    0

    Smile Pseudo-priorityQueue datastructure

    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.

    Last sidenote: first post on any programming forum so if I messed something up as far as forum courtesy goes, please be nice and let me know to correct it. I've just never posted to or read from any of these forums, so give me a break, yea?

  2. #2
    JosAH's Avatar
    JosAH is offline Moderator
    Join Date
    Sep 2008
    Location
    Voorschoten, the Netherlands
    Posts
    13,021
    Blog Entries
    7
    Rep Power
    20

    Default

    Does the suggestion supplied in the API documentation of that class help? Arrays.sort(pq.toArray()); it gives you a sorted array of your priority queue.

    kind regards,

    Jos
    Last edited by JosAH; 02-27-2011 at 12:32 PM.
    cenosillicaphobia: the fear for an empty beer glass

  3. #3
    couling is offline Member
    Join Date
    Nov 2010
    Posts
    54
    Rep Power
    0

    Default

    Yer the API suggests just sorting the whole thing. This is very inefficient if you're going to do this a lot with large sets.

    Your problem is that a PrioritoryQueue is only partially sorted (just enough to efficiently maintain which the next 1 element will be). The set continues to be sorted as you add and remove elements from the queue.

    If this is going to be repeatedly used in your program, may I suggest using a TreeSet or some other form of sorted set as these are completely sorted.
    ----Signature ----
    Please use [CODE] tags and indent correctly. It really helps when reading your code.

Similar Threads

  1. pseudo code
    By jamiem in forum New To Java
    Replies: 4
    Last Post: 12-20-2010, 05:25 PM
  2. Providing pseudo Webcam
    By H@CK3R in forum New To Java
    Replies: 21
    Last Post: 09-28-2010, 06:08 AM
  3. generate pseudo random numbers in java
    By csr81 in forum Advanced Java
    Replies: 3
    Last Post: 03-01-2010, 07:08 AM
  4. Replies: 7
    Last Post: 04-07-2009, 06:04 AM
  5. Any Datastructure Suggestions For An Unbalanced Tree?
    By markus-sukram in forum New To Java
    Replies: 0
    Last Post: 03-26-2008, 02:25 PM

Tags for this Thread

Posting Permissions

  • You may not post new threads
  • You may not post replies
  • You may not post attachments
  • You may not edit your posts
  •