CODEWITHSUNDEEP
javaalgorithmtime-complexityasymptotic-complexity
Gustavo
Gustavo

Reputation: 3801

How to insert values in descending order into a LinkedList in O(n log n) complexity?

I have to implement a custom ProperyQueue and I decided to use a LinkedList as a container for my values. The order in which are to be inserted is high value - low priority. Therefore the queue has the values in a descending order and the priority ascending as the element' values are smaller. How to implement the insertion method to use a complexity of O(n log n) ?

This is the priority queue : 

public class PriorityQueue<E extends Comparable<? super E>> implements Comparable {
    private LinkedList<E> queue;
    private int size;


    public PriorityQueue(int size) {
        this.size = size;
        queue = new LinkedList<>();
    }

    public PriorityQueue() {
        this(50000);
    }

  public void insert(E value) {
        if (queue.size() == size) {
            try {
                throw new SizeLimitExceededException();
            } catch (SizeLimitExceededException e) {
                e.printStackTrace();
            }
        }
        if (value == null) {
            throw new NullPointerException();
        } else {
            queue.add(value);
            size--;
        }
        Collections.sort(queue);
        Collections.reverse(queue);
    }

}

The complexity of my insertion method is O(n pow(n)) how can I improve it , what algorithm should I use ?

Upvotes: 0

Views: 272

Answers (1)

Robert Kock
Robert Kock

Reputation: 6028

Why don't you simply use a TreeSet?
The compareTo method of the individual elements should first compare the priority (returning a negative value for a higher priority) and then some compare on the other attributes in order to make them unique.

Upvotes: 1

Related Questions