Приоритетная очередь


Сложный уровень Легко
Часто спрашивают в Амазонка Avalara CodeNation Goldman Sachs Google Microsoft
Очередь теория

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

Пример

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

  1. A
  2. B
  3. A

В следующем порядке будет формироваться приоритетная очередь:

Приоритетная очередь Приоритетная очередь

Итак, вы видите, что задания с более высоким приоритетом назначаются перед заданиями с более низким приоритетом.

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

  1. Очередь с приоритетом в порядке возрастания

    В этом типе priority_queue более низкий приоритет назначается заданиям с более высоким приоритетом.
    Например: Если двум заданиям, а именно A и B, присвоены номера 1 и 2, где задание A имеет более высокий приоритет, тогда A будет присвоен 1, а заданию B будет назначено 2.

  2. Очередь с приоритетом в порядке убывания

    В этом типе priority_queue заданиям с более высоким приоритетом назначается номер с более высоким приоритетом.
    Например: Если двум заданиям, а именно A и B, присвоены номера 1 и 2, где задание A имеет более высокий приоритет, тогда A будет присвоен 2, а заданию B будет назначено 1.

Операция, выполняемая Priority Queue

Основные операции, выполняемые priority_queue, следующие:

  1. Вставка: Вставьте элемент в очередь в соответствии с его приоритетом.
  2. Удалить: Удаляет элемент из очереди.
  3. getHighestPriority: Дает вам элемент с наивысшим приоритетом.

Priority_queue поддерживает еще несколько операций:

  1. Заглянуть: Получите элемент впереди очереди.
  2. полный: проверяет, заполнена ли очередь.
  3. пустой: проверяет, пуста ли очередь.

Приложения

  1. В планировании, таком как планирование ЦП, планирование дисков и т. Д.
  2. Графические алгоритмы (алгоритм кратчайшего пути Дейкстры, минимальное связующее дерево Прима и т. Д.)

Реализация

Приоритетная очередь может быть реализована с использованием различных структур данных, таких как массив, связанный список и т. Д. Некоторые из структур данных приведены ниже с их временными сложностями:

  1. Массивы (O (n * log (n)))
  2. Связанный список (O (n)
  3. Куча (O (журнал (n)))

Из всех структур данных структура данных кучи обеспечивает лучшую временную сложность при реализации priority_queue.

дело