Структура данных — Приоритетная очередь
Приоритетная очередь — это расширение очереди. В отличие от принципа «первым пришёл — первым вышел» обычной очереди, каждому элементу приоритетной очереди назначается приоритет, и операция удаления из очереди всегда удаляет элемент с наивысшим приоритетом в текущей очереди.
Понятие и особенности приоритетной очереди
Это можно сравнить с системой медицинской сортировки в отделении неотложной помощи больницы — чем критичнее состояние пациента, тем раньше ему оказывают помощь, даже если он прибыл позже.
Основные операции приоритетной очереди отличаются от операций обычной очереди:
| Действие | Обычная очередь | Приоритетная очередь |
|---|---|---|
| Добавление в очередь | Добавить элемент в хвост | Вставить элемент с приоритетом |
| Извлечь из очереди | Вернуть элемент в голове (добавленный в очередь раньше всех) | Вернуть элемент с наивысшим приоритетом |
Сравнение трёх методов реализации
Неупорядоченный массив
Упорядоченный связный список
Куча ★ Рекомендуется
Реализация с помощью кучи оптимальна: она балансирует вставку и извлечение и является основной зависимостью таких алгоритмов, как алгоритм Дейкстры для поиска кратчайшего пути и кодирование Хаффмана.
На рисунке выше сравниваются различия во временной сложности трёх методов реализации; реализация с помощью кучи — наиболее сбалансированный выбор.
Реализация на основе неупорядоченного массива
Пример
#define MAX 100
/* Очередь с приоритетом на основе неупорядоченного массива (очередь с максимальным приоритетом: чем больше значение, тем выше приоритет) */
struct PriorityQueue {
int items[MAX];
int size; /* Текущее количество элементов */
};
void initPQ(struct PriorityQueue* pq) { pq->size = 0; }
/* Постановка в очередь: напрямую добавить в конец, O(1) */
void enqueue(struct PriorityQueue* pq, int value) {
if (pq->size >= MAX) return;
pq->items[pq->size++] = value;
}
/* Извлечение из очереди: пройти, чтобы найти максимум, O(n)
После его нахождения переместите последний элемент в удалённую позицию и уменьшите size на 1 */
int dequeue(struct PriorityQueue* pq) {
if (pq->size == 0) return -1;
/* Найти индекс максимального значения */
int maxIdx = 0;
for (int i = 1; i < pq->size; i++) {
if (pq->items[i] > pq->items[maxIdx]) {
maxIdx = i;
}
}
int maxVal = pq->items[maxIdx];
/* Переместить последний элемент на место удаляемого элемента (во избежание большого количества перемещений) */
pq->items[maxIdx] = pq->items[--pq->size];
return maxVal;
}
int main() {
struct PriorityQueue pq;
initPQ(&pq);
enqueue(&pq, 5);
enqueue(&pq, 9);
enqueue(&pq, 3);
enqueue(&pq, 7);
printf("Извлечение (наивысший приоритет): %d\n", dequeue(&pq)); /* Вывод: 9 */
printf("Извлечение (наивысший приоритет): %d\n", dequeue(&pq)); /* Вывод: 7 */
printf("Извлечение (наивысший приоритет): %d\n", dequeue(&pq)); /* Вывод: 5 */
printf("Извлечение: %d\n", dequeue(&pq)); /* Вывод: 3 */
return 0;
}
Реализация на основе упорядоченного связного списка
Пример
#include <stdlib.h>
struct Node {
int data;
int priority; /* Приоритет (чем больше значение, тем выше приоритет) */
struct Node* next;
};
/* Постановка в очередь: вставка в порядке убывания приоритета, O(n) */
struct Node* enqueue(struct Node* head, int data, int priority) {
struct Node* newNode = (struct Node*)malloc(sizeof(struct Node));
newNode->data = data;
newNode->priority = priority;
newNode->next = NULL;
/* Пустой список или новый узел имеет наивысший приоритет → вставка в начало */
if (head == NULL || head->priority < priority) {
newNode->next = head;
return newNode;
}
/* Пройти по списку, чтобы найти подходящую позицию (сохраняя убывающий порядок) */
struct Node* cur = head;
while (cur->next != NULL && cur->next->priority >= priority) {
cur = cur->next;
}
newNode->next = cur->next;
cur->next = newNode;
return head;
}
/* Извлечение из очереди: удалить головной узел (наивысший приоритет), O(1) */
struct Node* dequeue(struct Node* head) {
if (head == NULL) return NULL;
struct Node* temp = head;
printf("Извлечение из очереди: данные=%d, приоритет=%d\n", temp->data, temp->priority);
head = head->next;
free(temp);
return head;
}
int main() {
struct Node* pq = NULL;
pq = enqueue(pq, 10, 1); /* Данные 10, приоритет 1 */
pq = enqueue(pq, 20, 5); /* Данные 20, приоритет 5 */
pq = enqueue(pq, 30, 3); /* Данные 30, приоритет 3 */
pq = dequeue(pq); /* Dequeue: data=20, priority=5 (наивысший приоритет) */
pq = dequeue(pq); /* Dequeue: data=30, priority=3 */
pq = dequeue(pq); /* Dequeue: data=10, priority=1 */
return 0;
}
КучаВ настоящее время это наиболее распространённое и сбалансированное решение для реализации очередей с приоритетом — как вставка, так и удаление элемента с наивысшим приоритетом выполняются за время O(log n). Этот материал будет подробно рассмотрен в главе 15 о кучах.
Сценарии применения
| Сценарий | Описание |
|---|---|
| Планирование задач | Операционная система определяет порядок выполнения на CPU на основе приоритета задач. |
| Кратчайший путь Дейкстры | Каждый раз выбирается непосещённый узел с наименьшим расстоянием, полагаясь на очередь с приоритетом. |
| Кодирование Хаффмана | Повторно извлекаются два узла с наименьшей частотой и объединяются для построения оптимального дерева кодирования. |