如何在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)