Какова правильная структура данных для очереди, которая поддерживает операции Min, Max в O (1) раз?

Question

Какова правильная структура данных для очереди, поддерживающей операции Enque, Dequeue, Peak, Min и Max и выполняющая все эти операции в O (1) раз.

Наиболее очевидной структурой данных является связанный список, но Min, Max операций будет O (n). Priority Queue - еще один отличный выбор, но Enqueue, Dequeue должен работать обычным образом в очереди. (FIFO)

И еще один вариант, который приходит на ум - это куча, но я не могу понять, как можно создать очередь с помощью операции Min, Max с помощью Heaps.

Любая помощь очень ценится.

Answer 1

Структура данных, которую вы ищете, не может быть спроектирована, если min() и max() фактически меняют структуру. Если параметры min() и max() аналогичны peek() и предоставляют доступ только для чтения, то вы должны выполнить шаги в this question, добавив еще одну отметку, аналогичную той, которая используется для операций min() для использования в max() операция. Остальная часть этого ответа предполагает, что min() и max() фактически удаляют соответствующие элементы.

Поскольку вам требуются enqueue() и dequeue(), элементы должны быть добавлены и удалены по порядку прибытия (FIFO). Простая двойная очередь (связанная или использующая круговой вектор) обеспечит это в O (1).

Но элементы, которые необходимо добавить, могут изменять ток min() и max(); однако при удалении старые значения min() и max() должны быть восстановлены ... если только они не были удалены промежутком времени. Это ограничение заставляет вас как-то убирать элементы. Любая сортировочная структура (min-heap, max-heap, сбалансированное двоичное дерево, ...) потребует не менее O (log n), чтобы найти позицию нового прибытия.

Ваш лучший выбор - собрать сбалансированное двоичное дерево (для min() и max()) с двусвязным списком. Ваши узлы дерева будут хранить набор указателей на узлы списка, отсортированные по любой клавише, которую вы используете в min() и max(). В Java:

// N your node class; can return K, comparable, used for min() and max() 
LinkedList<N> list;   // sorted by arrival 
TreeMap<K,HashMap<N>> tree; // sorted by K 

• на enque(), можно добавить новый узел к концу list, и добавить тот же узел, ее ключом, к HashMap в узле tree. O (log n).
• на dequeue(), вы удалите узел с начала list и из его HashMap в своем узле в дереве. O (log n).
• на мин.(), вы искали бы 1-й элемент в дереве. O (1). Если вам нужно удалить его, у вас есть указатель на связанный список, поэтому O (1) с этой стороны; но O (log n), чтобы переустановить дерево, если оно было последним элементом с этим конкретным K.
• по max(), применяется та же логика; за исключением того, что вы будете искать последний элемент в дереве. Таким образом, O (log n).
• на peek(), смотря, но не извлекая 1-й элемент в очереди, будет O (1).

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

На практике разница между O (журнал N) и O (1) настолько мало, что реализация карты по умолчанию в C++ STL 's является O (журнал N) основанной (дерево вместо Hash).

Answer 2

Предположение:

, что вы заботитесь только о производительности, а не о пространстве/памяти/...

Готовили раствор:

То, что индекс представляет собой набор, а не список (будет работать для списка, но может потребоваться дополнительная любовь)

Вы можете сделать очередь и хеш-стол бок о бок.

Пример:

Допустим заказ 5 4 7 1 8 3

Очередь -> 547813

хэш-таблица -> 134578

Епдиеие:

1) Возьмите свой объект и вставьте в хэш-таблицу в правое ведро Min/Max всегда будет первым и последним индексом. (см. отсортированные хеш-таблицы)

2) Затем вставьте в свою очередь, как обычно.

3) Вы можете/должны связать эти два. Одной из идей было бы использовать значение хеш-таблицы в качестве указателя на очередь.

Обе операции с большой хеш-таблицы будет O (1)

Ведиеие:

1) Поп кулак элемент O (1)

2) удалить элемент из хэш-таблицы O (1)

Min/Max:

1) смотреть т х хеш-таблицу. В зависимости от используемого языка теоретически можно найти его, взглянув на голову стола или на хвост таблицы.

Для лучшего объяснения отсортированных хэш-таблиц, https://stackoverflow.com/questions/2007212

Примечания: Я хотел бы отметить, что не существует «нормальная» структура данных, которая будет делать то, что вы требуя, чтобы я не знаю. Однако это не означает, что это невозможно.Если вы попытаетесь реализовать структуру данных, скорее всего, вам придется сделать это для своих нужд и не сможете использовать имеющиеся текущие библиотеки. Вам может потребоваться использовать язык с очень низким уровнем, например, сборку, чтобы достичь этого, но, возможно, C или Java могут иметь возможность, если вы хорошо относитесь к этим языкам.

Успехов

EDITED: я не объяснить отсортированные хэш-таблицы, поэтому добавили ссылку на другой SO, чтобы объяснить их.

Answer 3

Эта структура НЕ существует!

Существует простой способ одобрить этот вывод.

Как мы все знаем, сложность задачи сортировки - O (nlogn). Но если структура вы сказали, существует, будет решением для сортировки:

1. Enque каждый элемент по одному стоит О (п)
2. Dequeue каждый максимум (или мин) элемент один на один затраты на О (п)

что означает, что сортировка проблема может быть решена с помощью O (N) .Но это НЕВОЗМОЖНОГО.

Answer 4

Любая структура данных, которая может извлекать Min или Max в O (1) время необходимо провести по крайней мере O (журнал п) на каждом Insert и Remove для поддержания элементов в частично отсортированном порядке. Структуры данных, которые достигают этого, называются очередями приоритетов.

Основные опоры очереди приоритетов Insert, Max и RemoveMax. Существует несколько способов их создания, но binary heaps work best.

Поддержка всех Insert, Min, RemoveMin, Max и RemoveMax с одной очереди приоритета является более сложным. Способ сделать это с единой структурой данных, адаптированной из двоичной кучи, описан в статье:

Atkinson, Michael D., et al. «Min-max heaps and generalized priority queues.» Связь ACM 29.10 (1986): 996-1000.

Быстро и эффективно с точки зрения памяти, но для правильной работы требуется хорошее обслуживание.