В информатике , очереди двухсторонняя приоритет (DEPQ) [1] или двойного состава кучи [2] является структура данных похожа на приоритетной очереди или кучи , но позволяет эффективно удалять как максимум и минимум, в соответствии с некоторая упорядоченность по ключам (элементам), хранящимся в структуре. Каждый элемент в DEPQ имеет приоритет или значение. В DEPQ можно удалять элементы как в возрастающем, так и в убывающем порядке. [3]
Операции [ править ]
Двусторонняя приоритетная очередь включает следующие операции:
- пусто()
- Проверяет, пуст ли DEPQ, и возвращает истину, если он пуст.
- размер()
- Возвращает общее количество элементов, присутствующих в DEPQ.
- getMin ()
- Возвращает элемент с наименьшим приоритетом.
- getMax ()
- Возвращает элемент с наивысшим приоритетом.
- положить ( х )
- Вставляет элемент x в DEPQ.
- removeMin ()
- Удаляет элемент с минимальным приоритетом и возвращает этот элемент.
- removeMax ()
- Удаляет элемент с максимальным приоритетом и возвращает этот элемент.
Если операция должна выполняться над двумя элементами, имеющими одинаковый приоритет, то выбирается элемент, вставленный первым. Кроме того, приоритет любого элемента может быть изменен после того, как он был вставлен в DEPQ. [4]
Реализация [ править ]
Двусторонние очереди приоритетов могут быть построены из сбалансированных двоичных деревьев поиска (где минимальный и максимальный элементы являются крайними левыми и крайними правыми листьями соответственно) или с использованием специализированных структур данных, таких как минимальная и максимальная куча и куча пар .
Общие методы получения очереди с двусторонним приоритетом из очередей с обычным приоритетом: [5]
Метод двойной структуры [ править ]
В этом методе поддерживаются две разные очереди приоритетов для min и max. Одни и те же элементы в обоих PQ показаны с помощью указателей соответствия.
Здесь минимальный и максимальный элементы - это значения, содержащиеся в корневых узлах минимальной и максимальной кучи соответственно.
- Удаление элемента min : выполните removemin () в минимальной куче и удалите ( значение узла ) в максимальной куче, где значение узла - это значение в соответствующем узле в максимальной куче.
- Удаление элемента max : выполните removemax () в максимальной куче и удалите ( значение узла ) в минимальной куче, где значение узла - это значение в соответствующем узле в минимальной куче.
Общая переписка [ править ]
Половина элементов находится в минимальном PQ, а другая половина - в максимальном PQ. Каждый элемент в min PQ имеет взаимно однозначное соответствие с элементом в max PQ. Если количество элементов в DEPQ нечетное, один из элементов сохраняется в буфере. [1] Приоритет каждого элемента в минимальном PQ будет меньше или равен соответствующему элементу в максимальном PQ.
Листовая переписка [ править ]
В этом методе только листовые элементы минимального и максимального PQ образуют соответствующие взаимно однозначные пары. Необязательно, чтобы нелистовые элементы входили в пару взаимно однозначного соответствия. [1]
Интервальные кучи [ править ]
Помимо вышеупомянутых методов соответствия, DEPQ можно эффективно получить с помощью интервальных куч. [6] Интервальная куча похожа на встроенную минимальную и максимальную кучу, в которой каждый узел содержит два элемента. Это полное двоичное дерево, в котором: [6]
- Левый элемент меньше или равен правому элементу.
- Оба элемента определяют замкнутый интервал.
- Интервал, представленный любым узлом, кроме корня, является подинтервалом родительского узла.
- Элементы с левой стороны определяют минимальную кучу .
- Элементы с правой стороны определяют максимальную кучу .
В зависимости от количества элементов возможны два случая [6] -
- Четное количество элементов: в этом случае каждый узел содержит два элемента, например, p и q , причем p ≤ q . Тогда каждый узел представлен интервалом [ p , q ].
- Нечетное количество элементов: в этом случае каждый узел, кроме последнего, содержит два элемента, представленных интервалом [ p , q ], тогда как последний узел будет содержать единственный элемент и представлен интервалом [ p , p ].
Вставка элемента [ править ]
В зависимости от количества элементов, уже присутствующих в куче интервалов, возможны следующие случаи:
- Нечетное количество элементов: если количество элементов в интервальной куче нечетное, новый элемент сначала вставляется в последний узел. Затем он последовательно сравнивается с предыдущими узловыми элементами и тестируется на соответствие критериям, необходимым для интервальной кучи, как указано выше. В случае, если элемент не удовлетворяет ни одному из критериев, он перемещается из последнего узла в корень, пока не будут выполнены все условия. [6]
- Четное количество элементов: если количество элементов четное, то для вставки нового элемента создается дополнительный узел. Если элемент попадает слева от родительского интервала, он считается находящимся в минимальной куче, а если элемент падает справа от родительского интервала, он считается в максимальной куче . Далее он последовательно сравнивается и перемещается от последнего узла к корню до тех пор, пока не будут выполнены все условия для интервальной кучи. Если элемент лежит в пределах интервала самого родительского узла, то процесс останавливается и там сам и перемещение элементов не происходит. [6]
Время, необходимое для вставки элемента, зависит от количества движений, необходимых для выполнения всех условий, и составляет O (log n ).
Удаление элемента [ править ]
- Элемент Min: в куче интервалов минимальным элементом является элемент слева от корневого узла. Этот элемент удаляется и возвращается. Чтобы заполнить вакансию, созданную слева от корневого узла, элемент из последнего узла удаляется и повторно вставляется в корневой узел. Затем этот элемент последовательно сравнивается со всеми левыми элементами нисходящих узлов, и процесс останавливается, когда выполнены все условия для интервальной кучи. В случае, если левый элемент в узле становится больше правого элемента на любом этапе, два элемента меняются местами [6], а затем выполняются дальнейшие сравнения. Наконец, корневой узел снова будет содержать минимальный элемент с левой стороны.
- Максимальный элемент: в интервальной куче максимальный элемент - это элемент с правой стороны корневого узла. Этот элемент удаляется и возвращается. Чтобы заполнить вакансию, созданную справа от корневого узла, элемент из последнего узла удаляется и повторно вставляется в корневой узел. Дальнейшие сравнения выполняются на аналогичной основе, как описано выше. Наконец, корневой узел снова будет содержать элемент max с правой стороны.
Таким образом, с помощью интервальных куч можно эффективно удалять как минимальный, так и максимальный элементы, переходя от корня к листу. Таким образом, DEPQ может быть получен [6] из интервальной кучи, где элементы интервальной кучи являются приоритетами элементов в DEPQ.
Сложность времени [ править ]
Интервальные кучи [ править ]
Когда DEPQ реализованы с использованием интервальных куч, состоящих из n элементов, временные сложности для различных функций сформулированы в таблице ниже [1]
| Операция | Сложность времени |
|---|---|
| в этом( ) | На) |
| пусто( ) | О (1) |
| getmin () | О (1) |
| getmax () | О (1) |
| размер( ) | О (1) |
| вставить (х) | O (журнал n ) |
| removeMin () | O (журнал n ) |
| removeMax () | O (журнал n ) |
Сопряжение кучи [ править ]
Когда DEPQ реализованы с использованием куч или парных куч, состоящих из n элементов, временные сложности для различных функций сформулированы в таблице ниже. [1] Для объединения куч это амортизированная сложность .
| Операция | Сложность времени |
|---|---|
| пусто( ) | О (1) |
| getmin () | О (1) |
| getmax () | О (1) |
| вставить (х) | O (журнал n ) |
| removeMax () | O (журнал n ) |
| removeMin () | O (журнал n ) |
Приложения [ править ]
Внешняя сортировка [ править ]
Одним из примеров применения двусторонней приоритетной очереди является внешняя сортировка . При внешней сортировке элементов больше, чем может храниться в памяти компьютера. Сортированные элементы изначально находятся на диске, а отсортированная последовательность должна оставаться на диске. Внешняя быстрая сортировка реализуется с помощью DEPQ следующим образом:
- Считайте столько элементов, сколько поместится во внутренний DEPQ. Элементы в DEPQ в конечном итоге станут средней группой (стержнем) элементов.
- Прочтите остальные элементы. Если следующий элемент ≤ наименьшего элемента в DEPQ, выведите этот следующий элемент как часть левой группы. Если следующий элемент ≥ самый большой элемент в DEPQ, выведите этот следующий элемент как часть правой группы. В противном случае удалите элемент max или min из DEPQ (выбор может быть сделан случайным образом или поочередно); если максимальный элемент удален, вывести его как часть правой группы; в противном случае вывести удаленный элемент как часть левой группы; вставьте новый элемент ввода в DEPQ.
- Выведите элементы в DEPQ в отсортированном порядке как среднюю группу.
- Рекурсивно отсортируйте левую и правую группы.
См. Также [ править ]
- Очередь (абстрактный тип данных)
- Приоритетная очередь
- Двусторонняя очередь
Ссылки [ править ]
- ^ a b c d e f g h Структуры данных, алгоритмы и приложения в Java: двухсторонние очереди приоритетов , Сартадж Сахни , 1999.
- Перейти ↑ Brass, Peter (2008). Расширенные структуры данных . Издательство Кембриджского университета. п. 211. ISBN. 9780521880374.
- ^ «Depq - очередь с двусторонним приоритетом» . Архивировано из оригинала на 2012-04-25 . Проверено 4 октября 2011 .
- ^ "depq" .
- ^ Основы структур данных в C ++ - Эллис Хоровиц, Сартадж Сахни и Динеш Мехта
- ^ Б с д е е г http://www.mhhe.com/engcs/compsci/sahni/enrich/c9/interval.pdf
