java - 如何在 java 中使用基本方法实现通用 PriorityQueue？

Question

我需要在不使用 PriorityQueue 形式的 Java.Util 的情况下实现自定义优先级队列...我有三种基本方法:插入、删除和清除。所有操作必须在常数时间 O (log n) 内完成。我怎样才能做到这一点？我应该为这些操作使用什么算法？最后，我应该使用哪种类型的容器来保存通用值？

这就是我到目前为止所做的......

public class PriorityQueue<E extends Comparable<? super E>> implements Comparable {
    private Stack<E> queue = new Stack<>();
    private int size;


    public PriorityQueue(int size) {
        this.size = size;
    }

    public PriorityQueue() {
        size = 50000;
    }

    public void insert(E value) {
        if (value == null) {
            throw new NullPointerException();
        }
        //how can I insert a value and what container should I use ?

    }

    public void remove() {
        //remove largest
    }

    public int compareTo(Object o) {
        if (o != null && o instanceof PriorityQueue) {
            PriorityQueue anotherQueue = (PriorityQueue) o;
            return this.size - anotherQueue.size;
        } else {
            throw new ClassCastException();
        }
    }
}

不多..但帮助将不胜感激!

Answer 1

我看到您的“删除”操作占用了最大的元素。似乎“最大堆”适合您的目的。

https://en.wikipedia.org/wiki/Heap_(data_structure)