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

Question

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

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

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

Спасибо.

Answer 1

Типичная реализация PriorityQueue будет использовать Heap для получения производительности O (lg n) для операции добавления, так что производительность O (n) будет еще проще.

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

Answer 2

метод queue () в O (1) и метод dequeue () в O (n):

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

метод queue () в O (n) и метод dequeue () в O (1):

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

Answer 3

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

Answer 4

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

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

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

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

Answer 5

В Википедии есть решение для этого -

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

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

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

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

http://www.java -forums.org / Java-языки / 7449-хау реализации приоритетной-очереди java.html

В приведенном выше примере для удаления очереди требуется O (1), а для вставки - O (n)

Answer 6

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

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

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