Извлечение последнего элемента приоритетной очереди без обхода
Задача состоит в том, чтобы извлечь последний элемент приоритетной очереди, не пересекая ее.
Подход:
Эту проблему можно решить с помощью очереди с двусторонним приоритетом , двусторонняя очередь с приоритетом поддерживает операции как с максимальной кучей (очередь с максимальным приоритетом), так и с минимальной кучей (очередь с минимальным приоритетом).
Операции:
- 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)
- Введение в двоичное дерево поиска - учебные пособия по структурам данных и алгоритмам