Структура данных Priority Queue и ее операции - Insert, Delete, Peek и Extract-Max.
Привет, друзья, это еще одна статья о структуре данных, в которой я собираюсь рассказать о структуре данных приоритет очередь. Я уже рассмотрел все алгоритмы сортировки и поиска. Вы можете найти их здесь". Я прошу вас прочитать и прокомментировать эти статьи, чтобы я мог улучшить их с течением времени.
Что такое приоритетная очередь?
Очередь с приоритетом - это тип очереди, в которой каждый элемент связан с приоритетом и удаляется из очереди в соответствии с его приоритетом. Если встречаются элементы с одинаковым приоритетом, они удаляются из очереди в соответствии с их порядком в очереди.
Как правило, значение самого элемента учитывается для присвоения приоритета элементу. В некоторых реализациях элемент с наивысшим значением считается элементом с наивысшим приоритетом. Однако в других реализациях элемент с наименьшим значением считается элементом с наивысшим приоритетом.
Соответствует ли приоритетная очередь нормальному правилу очереди?
В обычной очереди соблюдается правило «первым пришел - первым вышел», тогда как в очереди с приоритетом элементы удаляются на основе приоритета. Первым гаснет тот, у которого наивысший приоритет.
Как можно реализовать приоритетную очередь?
Есть несколько способов реализовать структуру данных очереди приоритетов. По сути, это может быть реализовано с использованием массивов, связанных списков, минимальной / максимальной двоичной кучи или двоичного дерева поиска. Реализация кучи обеспечивает лучшее время для операций просмотра, вставки и удаления. Я буду использовать максимальную кучу для реализации очереди с приоритетами.
Несколько замечаний по поводу сложностей:
- LinkedList, куча и BST занимают O (1) время для операции просмотра.
- LinkedList занимает O (n) и кучу, а BST занимает O (N log N) время для операции вставки.
- LinkedList занимает O (n) и кучу, а BST занимает O (N log N) время для операции удаления.
Давайте разберемся с работой очереди приоритетов:
Примечание. Я буду использовать максимальную кучу для реализации очереди с приоритетами. Прочтите эту статью, чтобы понять максимальную и минимальную кучу и процедуру heapify.
1. Операция вставки:
- Вставьте новый элемент в конец очереди приоритетов (то есть в двоичную максимальную кучу).
2. Заполните приоритетную очередь (max-heapify двоичную кучу).
2. Операция удаления:
- Выберите элемент, который нужно удалить из очереди приоритетов.
2. Поменяйте местами этот элемент с последним элементом очереди приоритета.
3. Удалите последний элемент из очереди приоритетов.
4. Увеличьте до максимума приоритетную очередь.
3. Операция Peek (определение макс. / Мин.):
Операция Peek возвращает максимальный элемент из Max Heap и минимальный элемент из Min Heap без удаления узла из очереди приоритетов (кучи).
И для максимальной кучи, и для минимальной кучи
return rootNode
4. Извлечение максимума / минимума из очереди приоритетов.
Extract-Max возвращает узел с максимальным значением после его удаления из Max Heap, тогда как Extract-Min возвращает узел с минимальным значением после удаления его из Min Heap.
Реализация приоритетной очереди:
Выход:
Queue is empty and cannot perform delete operation. Peek of the Queue is null Element 10 added. --------------------------------- Queue : 10 --------------------------------- Element 20 added. --------------------------------- Queue : 20 10 --------------------------------- Element 10 deleted successfully. --------------------------------- Queue : 20 --------------------------------- Element 30 added. --------------------------------- Queue : 30 20 --------------------------------- Peek of the Queue is 30 Element 40 added. --------------------------------- Queue : 40 20 30 --------------------------------- There is no such element 100 in the queue. Element 50 added. --------------------------------- Queue : 50 40 30 20 --------------------------------- Peek of the Queue is 50 Element 70 added. --------------------------------- Queue : 70 50 30 20 40 --------------------------------- Peek of the Queue is 70 Element 70 deleted successfully. --------------------------------- Queue : 50 40 30 20 --------------------------------- --------------------------------- Queue : 40 20 30 --------------------------------- Extract Max : 50
Анализ сложности:
- O (1) время для операции просмотра.
- O (nlogn) время для операции вставки.
- O (nlogn) время для операции удаления.
- O (nlogn) время для минимальной / максимальной операции извлечения.
Приложения Priority Queue:
- Стек может быть реализован с использованием очереди приоритетов.
- Для таких алгоритмов, как кодирование Дейкстры и Хаффмана для сжатия данных, может использоваться очередь приоритетов.
Спасибо, что прочитали эту статью. Надеюсь, эта статья оказалась для вас полезной. Вы можете прочитать следующие статьи о структурах данных и алгоритмах.
