如何按降序将值插入复杂度为 O(n log n) 的 LinkedList 中？

Question

我必须实现自定义 ProperyQueue，并且我决定使用 LinkedList 作为我的值的容器。插入的顺序是高价值 - 低优先级。因此，队列中的值按降序排列，并且随着元素的值越小，优先级越高。如何实现插入方法使用复杂度O(n log n) ?

这是优先队列：

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);
    }

}

我的插入方法的复杂度是O(n pow(n)) 我该如何改进它，我应该使用什么算法？

Answer 1

为什么不直接使用 TreeSet？
各个元素的 compareTo 方法应该首先比较优先级（返回负值以获得更高的优先级），然后对其他属性进行一些比较以使它们唯一。

如何按降序将值插入复杂度为 O(n log n) 的 LinkedList 中？

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

java

algorithm

time-complexity

asymptotic-complexity