Приоритетная очередь, сопоставимая

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

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

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

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

Answer 3

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