priority queue based on an unsorted sequence

Posted on 2006-05-27
Last Modified: 2012-06-27
Any idea or example of a Java implementation of a priority queue based on an unsorted sequence?
Question by:dbkattel
    LVL 86

    Accepted Solution

    This shows the queue, starting unordered, then how it orders itself:

     * 27-May-2006

    package misc;

     * @author Charles

    import java.util.PriorityQueue;

    public class PriorityQueueExample {

          public static void main(String args[]) {
                PriorityQueue<Integer> PQ = new PriorityQueue<Integer>();
                for (int i = 0; i < 10; i++) {
                      PQ.add((int)(Math.random() * 100));
                for (int i = 0; i < 10; i++) {
                      System.out.println("current head is: " + PQ.poll());
    LVL 14

    Assisted Solution

    LVL 92

    Assisted Solution

    LVL 4

    Assisted Solution

    A priority queue is an abstract data type with the following simple set of operations:

    add - adds a new element
    findMinimum or findMaximum - find the largest / smallest element
    deleteMinimum or deleteMaximum - remove the largest / smallest element

    You can easily implement this on top of a sequence.  As a simple example, you could just have a sequence underneath (completely unsorted, I presume that is what you mean by an unordered sequence).

    Adding an element would add to the end / beginning of a list, this would be either O(1) or O(n)

    Finding an element (and deleting an element) would be O(n) as you'd have to scan every element to find the right one.  This is the downside of not maintaining a sorted list.

    Given how inefficient this is, people tend to use a more sophisticated data structure, such as a heap or maintain a sorted list.


    Author Comment

    i am still looking forward for an appropriate solution (a working java program) for this problem.


    Featured Post

    IT, Stop Being Called Into Every Meeting

    Highfive is so simple that setting up every meeting room takes just minutes and every employee will be able to start or join a call from any room with ease. Never be called into a meeting just to get it started again. This is how video conferencing should work!

    Join & Write a Comment

    Suggested Solutions

    Title # Comments Views Activity
    Which XML parser should I used for my requirement 11 49
    Convert BufferedReader to File 1 49
    countX 22 50
    groovy example issue 10 34
    Java contains several comparison operators (e.g., <, <=, >, >=, ==, !=) that allow you to compare primitive values. However, these operators cannot be used to compare the contents of objects. Interface Comparable is used to allow objects of a cl…
    Java Flight Recorder and Java Mission Control together create a complete tool chain to continuously collect low level and detailed runtime information enabling after-the-fact incident analysis. Java Flight Recorder is a profiling and event collectio…
    Viewers will learn about the different types of variables in Java and how to declare them. Decide the type of variable desired: Put the keyword corresponding to the type of variable in front of the variable name: Use the equal sign to assign a v…
    The viewer will learn how to implement Singleton Design Pattern in Java.

    733 members asked questions and received personalized solutions in the past 7 days.

    Join the community of 500,000 technology professionals and ask your questions.

    Join & Ask a Question

    Need Help in Real-Time?

    Connect with top rated Experts

    22 Experts available now in Live!

    Get 1:1 Help Now