СТРУКТУРА ДАННЫХ — СТЕК И ОЧЕРЕДЬ
Визуализируйте, спроектируйте и проанализируйте структуру данных приоритетной очереди
Структура данных Priority Queue и ее операции — Insert, Delete, Peek и Extract-Max.
Здравствуйте, это еще одна статья о структуре данных, в которой я собираюсь рассказать о структуре данных priority queue. Я уже рассмотрел все алгоритмы сортировки и поиска.
Вы можете найти их здесь. Я прошу вас прочитать и прокомментировать эти статьи, чтобы я мог улучшить их за этот период.
Что такое приоритетная очередь?
Очередь с приоритетом — это тип очереди, в которой каждый элемент связан с приоритетом и удаляется из очереди в соответствии с его приоритетом. Если встречаются элементы с одинаковым приоритетом, они удаляются из очереди в соответствии с их порядком в очереди.
Как правило, значение самого элемента рассматривается для назначения приоритета элементу. В некоторых реализациях элемент с наивысшим значением считается элементом с наивысшим приоритетом. Однако в других реализациях элемент с наименьшим значением считается элементом с наивысшим приоритетом.
Соответствует ли приоритетная очередь правилам обычной очереди?
В обычной очереди соблюдается правило «первым пришел — первым вышел», тогда как в приоритетной очереди элементы удаляются на основе приоритета. Первым уходит тот, у кого наивысший приоритет.
Каковы способы реализации приоритетной очереди?
Существует несколько способов реализации структуры данных очереди приоритетов. По сути, это может быть реализовано с использованием массивов, связанных списков, минимальной/максимальной двоичной кучи или двоичного дерева поиска. Реализация кучи обеспечивает лучшее время для операций просмотра, вставки и удаления. Я буду использовать max heap для реализации приоритетной очереди.
Несколько замечаний о сложностях:
- LinkedList, куча и BST занимают O(1) время для операции просмотра.
- LinkedList занимает O(n) и кучу, а BST занимает O(nlogn) время для операции вставки.
- LinkedList занимает O(n) и кучу, а BST занимает O(nlogn) время для операции удаления.
Давайте разберемся с работой приоритетной очереди:
Примечание. Я буду использовать максимальную кучу для реализации приоритетной очереди. Прочтите эту статью, чтобы понять максимальную и минимальную кучу и процедуру heapify.
1. Операция вставки:
- Вставьте новый элемент в конец приоритетной очереди (т. е. в максимальную двоичную кучу).
2. Увеличьте очередь приоритетов (max-heapify бинарную кучу).
2. Удалить операцию:
- Выберите элемент, который необходимо удалить из очереди приоритетов.
2. Поменять местами этот элемент с последним элементом приоритетной очереди.
3. Удалить последний элемент из приоритетной очереди.
4. Максимально увеличить приоритетную очередь.
3. Операция просмотра (нахождение максимума/минимума):
Операция просмотра возвращает максимальный элемент из максимальной кучи и минимальный элемент из минимальной кучи без удаления узла из приоритетной очереди (кучи).
Как для максимальной кучи, так и для минимальной кучи
return rootNode
4. Извлечь-Max/Min из приоритетной очереди
Extract-Max возвращает узел с максимальным значением после его удаления из максимальной кучи, тогда как Extract-Min возвращает узел с минимальным значением после его удаления из минимальной кучи.
Реализация приоритетной очереди:
Выход:
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)время операции извлечения мин./макс.
Применение приоритетной очереди:
- Стек может быть реализован с использованием приоритетной очереди.
- Для таких алгоритмов, как кодирование Дейкстры и Хаффмана для сжатия данных, может использоваться приоритетная очередь.
Это все, что касается этой статьи. Надеюсь, вам понравилась эта статья.
