Извлечение последнего элемента приоритетной очереди без обхода

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

Подход:

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

Операции:

• getMax(): Returns maximum element.
• getMin(): Returns minimum element.
• deleteMax(): Deletes maximum element.
• deleteMin(): Deletes minimum element.
• size(): Returns count of elements.
• isEmpty(): Returns true if the queue is empty.

Подход к извлечению последнего элемента приоритетной очереди без обхода:

Мы можем использовать следующие две структуры данных для реализации функциональности.

Связанные списки:

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

Кучи :

Мы можем попробовать использовать две кучи (мин.кучу и макс.кучу). Основная идея состоит в том, чтобы поддерживать однозначное соответствие, так что deleteMin() и deleteMax() могут выполняться за время O(log n). Решение на основе кучи требует O(n) дополнительного пространства для дополнительной кучи. Преимущество решения на основе кучи — дружественность к кэшу.

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

Самобалансирующееся двоичное дерево поиска:

Здесь мы реализуем двустороннюю приоритетную очередь, используя самобалансирующееся двоичное дерево поиска. Самобалансирующийся BST реализован как набор в C++ и TreeSet в Java. Выполните следующие шаги, чтобы реализовать приоритетную очередь, в которой мы можем получить последний элемент без обхода.

• Создайте класс структуры с именем DblEndedPQ , который содержит все операции очереди с двойным приоритетом.
• Инициализировать мультимножество st . [Мы используем мультимножество, потому что элементы, вставленные в мультимножество, сортируются автоматически, как очередь с приоритетом, в соответствии с необходимостью.]
• Затем создайте обязательные операции, такие как:
  • размер()
  • пустой(),
  • вставлять(),
  • получитьмин()
  • получитьМакс()
  • получитьмин()
  • удалитьмин()
  • удалитьМакс()

Ниже приведена реализация вышеуказанного подхода:

Сложность времени :

• получитьМакс() : О(1)
• получитьМин() : О(1)
• deleteMax() : O(Log n)
• deleteMin() : O(Log n)
• размер () : O (1)
• isEmpty() : О(1)

Вспомогательное пространство : O(N)

Статьи по Теме:

• Что такое приоритетная очередь | Введение в приоритетную очередь
• Структура данных кучи
• Мультинабор в стандартной библиотеке шаблонов C++ (STL)
• Введение в двоичное дерево поиска - учебные пособия по структурам данных и алгоритмам