Wie implementiert man eine generische PriorityQueue mit grundlegenden Methoden in Java?

Question

Ich muss eine benutzerdefinierte Prioritätswarteschlange implementieren, ohne das PriorityQueue-Formular Java.Util zu verwenden ... Ich habe drei grundlegende Methoden: Einfügen, Entfernen und Löschen. Alle Operationen müssen in konstanter Zeit O (log n) durchgeführt werden. Wie kann ich das erreichen? Welche Algorithmen sollte ich für diese Operationen verwenden? Und zu welcher Art von Container soll ich die generischen Werte behalten?

Das ist, was ich bisher ...

getan haben

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

nicht viel .. aber Hilfe wäre sehr dankbar!

Answer 1

Ich sehe Ihre 'Entfernen' Operation nimmt das größte Element. Es scheint, als würde ein "Max Heap" zu deinen Zwecken passen.

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