Структура как приоритетная очередь, но с чем-то вроде нижней границы

Я хочу, чтобы структура сохраняла (например) числа, в которые я могу вставлять и удалять элементы, моя структура всегда сортируется (как очередь с приоритетами), НО с возможностью узнать, где находится данное число, и каждую операцию в логарифмическом времени.

Может быть, с lower_bound, upper_bound или просто с двоичным поиском, но в priority_queue я не могу получить доступ к элементам с индексом, только к первому.

Источник

2 ответа

Решение

Я думаю, что вы ищете дерево статистики заказов, расширенный BST, который поддерживает все обычные операции BST за время O(log n), а также два других:

  • rank (elem): вернуть, какой индекс elem будет занимать в отсортированной последовательности.
  • index (k): с учетом индекса k вернуть элемент по этому индексу в отсортированной последовательности.

Две вышеуказанные операции выполняются за O(log n), что делает их чрезвычайно быстрыми.

Вы можете рассматривать дерево статистики заказов как приоритетную очередь. Вставки работают как обычные вставки BST, и для извлечения наименьшего / наивысшего элемента вы просто удаляете наименьший / наибольший элемент из дерева, что вы можете сделать за время O(log n), просто спускаясь по левым или правым спинам дерева,

Источник

Приоритетная очередь не хранит вещи в отсортированном порядке. По крайней мере, не типично. Очередь приоритетов позволяет вам быстро получить следующий элемент в последовательности. Но вы не можете эффективно получить доступ, скажем, к 5-му элементу в очереди.

Мне известны три различных способа построения очереди с приоритетами, в которых вы можете эффективно получать доступ к элементам по ключу:

  • Используйте сбалансированное двоичное дерево поиска для реализации очереди. Хотя все операции выполняются за O(log n), типичное время выполнения медленнее, чем двоичная куча.
  • Реализуйте очередь с приоритетом кучи в виде списка пропусков. Это хороший вариант. Я видел, как некоторые люди сообщают, что очередь с приоритетами пропуска списка превосходит двоичную кучу. Поиск [C++ skip list] вернет вам множество реализаций.
  • То, что я называю индексированной двоичной кучей, также работает. По сути, вы сочетаете хеш-карту или словарь с двоичной кучей. Карта индексируется по ключу, и ее значение содержит индекс элемента в массиве кучи. Такую вещь не сложно построить, и она достаточно эффективна.
  • Если подумать, вы можете сделать индексированную версию кучи любого типа.

У вас есть несколько вариантов. Мне самому нравится список пропусков, но ваш пробег может отличаться.

Индексированная двоичная куча, как я указал, представляет собой гибридную структуру данных, которая поддерживает словарь (хэш-карту) и двоичную кучу. Кратко как это работает:

Ключ словаря - это поле, которое вы используете для поиска элемента, который вы помещаете в кучу. Значение является целым числом: индекс этого элемента в куче.

Сама куча - это стандартная двоичная куча, реализованная в массиве. Разница лишь в том, что каждый раз, когда вы перемещаете элемент из одного места в другое в куче, вы обновляете его местоположение в словаре. Так, например, если вы поменяете местами два элемента, вам придется поменять местами не только сами элементы в массиве, но и их позиции, хранящиеся в словаре. Например:

heap is an array of string references
dict is a dictionary, keyed by string

swap (a, b)
{
    // swap item at heap[a] with item at heap[b]
    temp = heap[a]
    heap[a] = heap[b]
    heap[b] = temp
    // update their positions in the dictionary
    dict[heap[a]] = b
    dict[heap[b]] = a
}

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

Это также можно сделать с помощью куч на основе узлов, таких как куча сопряжения, куча Фибоначчи, куча перекоса и т. Д.

Источник
Другие вопросы по тегам