очередь приоритет, Сопоставимые

Question

я должен написать priotity queye в реализации на следующие интерфейса:

public interface PQueue<T extends Comparable<T>> { 
    public void insert(T o); // inserts o into the queue 
    public T remove();   // removes object with highest priority (by natural order) 
} 

Я бы рад за некоторую помощь и подсказки, becouse я даже не знаю, как начать с этого вопрос.

Answer 1

Я бы начал с чего-то подобного. Основная идея состоит в том, что у вас есть внутренний список, и когда вы вставляете новый элемент, вы выполняете двоичный поиск, чтобы найти, где он принадлежит в этом списке. Таким образом, ваш внутренний список всегда сортируется, поэтому, когда вы вызываете remove(), вы просто берете последний (или первый в зависимости от того, как вы заказываете вещи).

Отказ от ответственности: Это следует рассматривать как псевдокод. Я знаю, что есть проблемы с этим. Он предназначен только для начала.

public class PQueueImpl<T> implements PQueue<T> { 
    private List<T> internalQueue; 

    public void insert(T item){ 
     int insertionPoint = Collections.binarySearch(internalQueue, item); 
     internalQueue.add(insertionPoint, item); 
    } 

    public T remove(){ 
     return internalQueue.remove(internalQueue.size() - 1); 
    } 
} 

Answer 2

Вы можете посмотреть на источник java.util.PriorityQueue. Их реализация поддерживается массивом Object и значительно сложнее, чем в другом примере, который я дал, но я уверен, что он работает и работает намного лучше.

Answer 3

Приоритетные очереди на практике реализованы чаще всего как heaps. Они также могут быть реализованы как сбалансированные binary search tree или любые другие быстро отсортированные структуры данных. Ключ состоит в том, что структура данных должна быть очень быстрой (быстрее, чем O (n)) max/min, вставлять, удалять и обновлять операции.