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

Опубликовано: 20 Февраля, 2023

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

Подход:

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

Операции:

  • 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)
  • Введение в двоичное дерево поиска - учебные пособия по структурам данных и алгоритмам