Рубрики

Очередь приоритетов | Комплект 1 (Введение)

Приоритетная очередь — это расширение очереди со следующими свойствами.

  1. Каждый элемент имеет приоритет, связанный с ним.
  2. Элемент с высоким приоритетом исключается перед элементом с низким приоритетом.
  3. Если два элемента имеют одинаковый приоритет, они обслуживаются в соответствии с их порядком в очереди.

В приведенной ниже очереди приоритетов элемент с максимальным значением ASCII будет иметь самый высокий приоритет.

Типичная очередь приоритетов поддерживает следующие операции.
insert (item, priority): вставляет элемент с заданным приоритетом.
getHighestPriority (): возвращает элемент с наивысшим приоритетом.
deleteHighestPriority (): удаляет элемент с наивысшим приоритетом.

Как реализовать приоритетную очередь?
Использование массива: простая реализация заключается в использовании массива следующей структуры.

struct item {
   int item;
   int priority;
}

Операция insert () может быть реализована путем добавления элемента в конец массива за O (1).

Операция getHighestPriority () может быть реализована путем линейного поиска элемента с наивысшим приоритетом в массиве. Эта операция занимает O (n) времени.

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

Мы также можем использовать Linked List, временная сложность всех операций со связанным списком остается такой же, как у массива. Преимущество связанного списка в том, что deleteHighestPriority () может быть более эффективным, поскольку нам не нужно перемещать элементы.

Используя кучи:
Куча обычно предпочтительна для реализации очереди с приоритетами, поскольку кучи обеспечивают лучшую производительность по сравнению массивов или связанных списков. В двоичной куче getHighestPriority () может быть реализовано за время O (1), insert () может быть реализовано за время O (Logn), а deleteHighestPriority () также может быть реализовано за время O (Logn).
С помощью кучи Фибоначчи insert () и getHighestPriority () могут быть реализованы за время амортизации O (1), а deleteHighestPriority () может быть реализовано за время амортизации O (Logn).

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

Очередь с приоритетами реализована с использованием кучи. Пожалуйста, обратитесь к статьям ниже для нашей собственной реализации и реализации библиотек.

  1. Двоичная куча (наиболее распространенная реализация очереди с приоритетами)
  2. Очередь приоритетов в C ++ .
  3. Очередь приоритетов в Java.
  4. Очередь приоритетов в Python.
  5. Очередь приоритетов в JavaScript.

Полезные ссылки :

  1. Последние статьи о Очередь Приоритетов!
  2. Приложения приоритетной очереди.

Ссылки:
http://en.wikipedia.org/wiki/Priority_queue

Пожалуйста, пишите комментарии, если вы обнаружите что-то неправильное или вы хотите поделиться дополнительной информацией по обсуждаемой выше теме.

Рекомендуемые посты:

Очередь приоритетов | Комплект 1 (Введение)

0.00 (0%) 0 votes