Реализация интерфейса очереди приоритетов Java

Question

Это были вопросы, которые меня задавали в интервью несколько дней назад, и я не был уверен в этом подходе. Предложения были бы весьма полезными:

Как я могу реализовать интерфейс PriorityQueue, чтобы получить метод queue() в методах O (1) и dequeue() в O (n).

Как я могу реализовать интерфейс PriorityQueue для получения метода queue() в методах O (n) и dequeue() в O (1).

Спасибо.

Answer 1

Обычная реализация PriorityQueue будет использовать кучу для получения O (lg n) производительности для операции «добавить», поэтому производительность O (n) будет еще проще.

Например, вы можете использовать вектор или связанный список в качестве базовой структуры данных. Для O (1) «добавить» вы можете просто добавить новое значение в конец, а для O (n) «удалить» вы можете выполнить линейный поиск минимального значения. И наоборот, для O (n) «add» вы можете выполнить линейное сканирование, чтобы найти следующее наибольшее значение, а затем вставить перед ним, для удаления O (1) вы можете просто удалить первый элемент списка.

Answer 2

Для подхода O (1) к способу queue() вы должны отслеживать последний элемент вашей очереди, чтобы вы могли легко добавить еще одно после него, независимо от размера вашей очереди.

Для функции O (n) в очереди() и O (1) в dequeue() вам необходимо отслеживать первый элемент вашей очереди в переменной, так что независимо от количества элементов внутри нее вы может удалить первый из списка с всегда одним набором инструкций (без итераций).

В каждом из обоих случаев вы добавляете только одну дополнительную переменную в свой класс.

Answer 3

Просто взгляните на:

http://www.docjar.com/html/api/java/util/PriorityQueue.java.html

Помните, что все хорошие программисты скопировать хороший код: P

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

метод

Answer 4

очереди() в O (1) и метод Dequeue() в О (п):

Используйте связанный список и просто добавить каждую новую запись непосредственно к главе списка в очереди(). В dequeue() переберите список и удалите и верните запись с наивысшим приоритетом.

метод

очереди() в O (N) и способ удаления из очереди() в O (1):

Используйте связанный список снова. Но на этот раз в queue() вы перебираете записи, чтобы поместить новую запись в ее отсортированную по приоритету позицию (это на самом деле один шаг сортировки вставки). В dequeue() вы можете всегда удалять и возвращать первый элемент списка.

Answer 5

Я бы сказал, что PriorityQueue не является интерфейсом, это класс, и я бы не реализовал ничего, что было O (n), если бы я мог ему помочь.

Answer 6

Википедия имеет решение для this--

http://en.wikipedia.org/wiki/Priority_queue#Naive_implementations

Для O (1) вставки, добавить элемент к текущему местоположению и DEQUEUE в O (N) выполняет поиск на основе приоритета ..

для O (N) вставки выполняют поиск изначально в зависимости от приоритета и добавить элемент и DEQUEUE в O (1) просто удалить элемент из начала или с 0-го места ...

код в этот пример может помочь вам лучше понять.

http://www.java-forums.org/java-lang/7449-how-implement-priority-queue-java.html

В приведенном выше примере, Dequeue занимает O (1) и вставка занимает O (N)