Превратите очередь в приоритетную очередь

Что такое очередь?

Queue is an abstract data type that is open at both ends. One end is always used to insert data (enqueue) which is basically the rear/back/tail end and the other which is the front end is used to remove data (dequeue). Queue follows First-In-First-Out (FIFO) methodology, i.e., “the data item stored first will be accessed first”.

Декларация:

queue<data_type> name

Что такое приоритетная очередь?

Priority Queue is an abstract data type that is similar to a queue, and every element has some priority value associated with it. The priority of the elements in a priority queue determines the order in which elements are served. If in any case, the elements have the same priority, they are served as per their ordering in the queue.

Декларация:

priority_queue<data_type> name

Типы приоритетной очереди:

Приоритетная очередь по возрастанию

Как следует из названия, в очереди с возрастающим приоритетом элемент с более низким значением приоритета получает более высокий приоритет в списке приоритетов. Например, если у нас есть следующие элементы в очереди приоритетов, расположенные в порядке возрастания, например {4, 6, 8, 9, 10}. Здесь 4 — самое маленькое число. Следовательно, он получит наивысший приоритет в очереди приоритетов.

По убыванию Приоритетная очередь

В очереди с убывающим приоритетом элементы с более высоким значением приоритета получают более высокий приоритет. Например, если у нас есть приоритетная очередь со значениями {10, 4, 3, 2}, элементу 10 будет присвоен наивысший приоритет, поскольку он имеет наибольшее значение.

Превращение очереди в приоритетную очередь

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

Пример :

Input : Q = [ 3, 4, 2, 8, 1, 7 ]
Output : Q =[ 8, 7, 4, 3, 2, 1 ]

Подход :

The idea is to sort the queue elements either in ascending / descending order. We know that queue can be sorted using recursion that takes extra space due to function call stack.

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

• Создайте очередь q и поместите в нее случайные элементы.
• Создайте функцию sortqueue для сортировки массива.
  • Если очередь пуста, возвращайтесь обратно.
  • Инициализируйте переменный элемент и сохраните в нем самый верхний элемент очереди и извлеките его из очереди.
  • Снова сделайте рекурсивный вызов внутри функции sortqueue .
• Теперь снова вставьте элементы в очередь, проверив, является ли q пустым или нет.
  • Если очередь пуста, поместите переднее значение внутрь очереди.
  • Проверьте, больше ли текущий элемент, чем элемент впереди.
    • Если да, то поместите значение внутрь очереди и сделайте рекурсивный вызов для вставки переднего элемента очереди в последний.
      • Если q не пусто, вернитесь назад.
      • Выдвиньте передний элемент и вставьте последний из очереди.
      • Делайте рекурсивные вызовы для дальнейших элементов.
    • В противном случае поместите передний элемент в последний в очереди и сделайте рекурсивный вызов для помещения элементов внутрь очереди.

Ниже приведена реализация описанного выше подхода.

Временная сложность : O(N ² )
Вспомогательное пространство : O(N)

Статьи по Теме:

• Что такое приоритетная очередь | Введение в приоритетную очередь
• Введение в очередь — учебные пособия по структуре данных и алгоритмам