Обратите внимание на другие наши ресурсы: Youtube | Telegram | VK | Rutube | Dzen | Boosty

Очередь с приоритетом

Очередь с приоритетом — это структура данных, которая работает по принципу «первым пришел, первым вышел» (FIFO), но с добавлением приоритетов для каждого элемента. Элементы с более высоким приоритетом будут удаляться из очереди раньше, чем элементы с более низким приоритетом, независимо от того, в каком порядке они были добавлены.

Особенностями реализации очереди с приоритетом будут являться фиктивные элементы, которые будут стоять в начале и в конце очереди. В начале очереди всегда стоит элемент с бесконечным положительным приоритетом, а в конце - с бесконечно отрицательным приоритетом. Эти особенности позволяют упростить реализацию.

---

Сферы применения

1. Операционные системы. Планировщики задач используют очереди с приоритетом для управления выполнением процессов.
2. Сети. В сетевых протоколах используются очереди с приоритетом для обработки данных с разными уровнями важности.

---

Операции

Очередь с приоритетом поддерживает следующие операции:

1. Добавление элемента ($push$) — добавляет элемент в очередь в соответствии с его приоритетом. Вычислительная сложность - $O(n)$ Пространственная сложность - $O(1)$

2. Удаление элемента ($pop$) — удаляет элемент из начала очереди. Вычислительная сложность - $O(1)$ Пространственная сложность - $O(1)$

3. Проверка очереди на пустоту ($is\_empty$) — позволяет узнать, есть ли в какие-либо элементы. Вычислительная сложность - $O(1)$ Пространственная сложность - $O(1)$

4. Получение размера ($size$) — возвращает текущее количество элементов в очереди. Вычислительная сложность - $O(1)$ Пространственная сложность - $O(1)$

5. Просмотр элемента с наивысшим приоритетом ($peek$) - возвращает элемент с наивысшим приоритетом, не удаляя его из очереди. Вычислительная сложность - $O(1)$ Пространственная сложность - $O(1)$

---

Добавление элемента

Пусть есть очередь:

Добавим в эту очередь элемент со значением = 50 и приоритетом = 3.

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

Такая расстановка элементов неверна, потому что приоритет нового элемента меньше приоритета следующего элемента.

Очередь после помещения нового элемента на правильную позицию выглядит следующим образом:

• Временная сложность: $O(n)$

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

• Пространственная сложность: $O(1)$

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

Добавление элементаh(значение, приоритет):
    Новый_узел = Узел(значение, приоритет)
    
    Текущий_элемент = Начало_очереди.следующий_элемент

    пока Текущий_элемент.приоритет >= Новый_узел.приоритет
        Текущий_элемент = Текущий_элемент.следующий_элемент

    Предыдущий_узел = Текущий_элемент.предыдущий_элемент
    Новый_узел.следующий_элемент = Текущий_элемент
    Новый_узел.предыдущий_элемент = Предыдущий_узел
    Предыдущий_узел.следующий_элемент = Новый_узел
    Текущий_элемент.предыдущий_элемент = Новый_узел

    Размер+=1

---

Удаление элемента

Пусть есть очередь:

В этой операции из очереди удаляется элемент с наибольшим приоритетом.

Как будет выглядеть очередь после выполнения операции:

• Временная сложность: $O(1)$ Удаление происходит с головы очереди, где элемент с наивысшим приоритетом находится сразу после фиктивного элемента head. Эта операция включает простое изменение указателей на следующий и предыдущий элементы, что занимает постоянное время.

• Пространственная сложность: $O(1)$ При удалении освобождается память, занимаемая одним узлом, что не требует дополнительной памяти.

Удаление элемента():
    если Очередь_пуста():
        Ошибка "Попытка извлечения элемента из пустой очереди"

    Элемент_с_наивысшим_приоритетом = Начало_очереди.следующий_элемент

    Следующий_узел = Элемент_с_наивысшим_приоритетом.следующий_элемент
    Начало_очереди.следующий_элемент = Следующий_узел
    Следующий_узел.предыдущий_элемент = Начало_очереди

    Размер-=1

    вернуть Элемент_с_наивысшим_приоритетом.значение

---

Проверка очереди на пустоту

Эта операции проверяет очередь на пустоту. Если в очереди нет элементов, то эта операция возвращает "Правда", иначе операция вернёт "Ложь".

Пусть есть очередь:

В очереди есть элементы, поэтому операция вернёт "Ложь".

• Временная сложность: $O(1)$ Проверка состоит в проверке того, что между фиктивным началом и фиктивным концом нет реальных элементов. Это делается проверкой указателей self.head.next == self.tail, что занимает постоянное время.

• Пространственная сложность: $O(1)$ Эта операция не требует дополнительного пространства.

Очередь_пуста():
    если Начало_очереди.следующий_элемент = Конец_очереди:
        вернуть Правда
        
    иначе:
        вернуть Ложь    

---

Получение размера

Эта операция возвращает размер очереди - количество элементов в ней.

Пусть есть очередь:

!

В очереди всего два элемента, поэтому операция вернёт число $2$.

• Временная сложность: $O(1)$ Количество элементов хранится в переменной size, так что операция возвращает его значение напрямую без необходимости пересчитывать элементы.

• Пространственная сложность: $O(1)$ Операция не требует дополнительной памяти, так как мы просто возвращаем значение уже существующей переменной.

Получение размера():
    вернуть Размер

---

Просмотр элемента с наивысшим приоритетом

Пусть есть очередь:

Эта операция вернёт значение элемента с наивысшим приоритетом, то есть элемента стоящего после начала очереди.

• Временная сложность: $O(1)$ Для этой операции необходимо обратиться к первому реальному элементу в списке, который находится сразу после фиктивного начала очереди. Это доступ по прямому указателю, который выполняется за постоянное время.

• Пространственная сложность: $O(1)$ Операция не требует дополнительного пространства.

Просмотр элемента с наивысшим приоритетом():
    если Очередь_пуста():
        вернуть Ошибка
        
    иначе:
        вернуть Начало_очереди.следующий_элемент.значение    

---

Псевдокод

Класс Узел (значение = пустота, приоритет = пустота, ссылка на следующий элемент = пустота, ссылка на предыдущий элемент = пустота):
    Значение
    Сслыка на следующий элемент
    Ссылка на предыдущий элемент
    Приоритет

Класс Очередь с приоритетом():
    Размер = 0
    Конец <- Узел(приоритет = -бесконечность)
    Начало <- Узел(приоритет = +бесконечность, следующий = конец)

    Добавить_элемент(значение, приоритет):
        Новый_узел = Узел(значение, приоритет)
        Текущий_элемент = Начало_очереди.следующий_элемент
    
        пока Текущий_элемент.приоритет >= Новый_узел.приоритет
            Текущий_элемент = Текущий_элемент.следующий_элемент
    
        Предыдущий_узел = Текущий_элемент.предыдущий_элемент
        Новый_узел.следующий_элемент = Текущий_элемент
        Новый_узел.предыдущий_элемент = Предыдущий_узел
        Предыдущий_узел.следующий_элемент = Новый_узел
        Текущий_элемент.предыдущий_элемент = Новый_узел

        Размер+=1

    Удалить_элемент():
        если Очередь_пуста():
            Ошибка "Попытка извлечения элемента из пустой очереди"
    
        Элемент_с_наивысшим_приоритетом = Начало_очереди.следующий_элемент
    
        Следующий_узел = Элемент_с_наивысшим_приоритетом.следующий_элемент
        Начало_очереди.следующий_элемент = Следующий_узел
        Следующий_узел.предыдущий_элемент = Начало_очереди
    
        Размер-=1
    
        вернуть Элемент_с_наивысшим_приоритетом.значение

    Просмотреть_элемент_с_наивысшим_приоритетом():
        если Очередь_пуста():
            вернуть Ошибка
            
        иначе:
            вернуть Начало_очереди.следующий_элемент.значение

    Очередь_пуста():
        если Начало_очереди.следующий_элемент = Конец_очереди:
            вернуть Правда
            
        иначе:
            вернуть Ложь

    Получить_размер():
        вернуть Размер

---

Реализация на Python

Аннотация:
Node - узел
data - данные, хранящиеся в узле
priority - приоритет узла
next - указатель на следующий элемент в очереди
prev - указатель на предыдущий элемент в очереди
PriorityQueue - очередь с приоритетом
head - начало очереди
tail - конец очереди
_size - размер очереди
push - метод добавления элемента в очередь
new_element - добавляемый в очередь элемент
current - текущий элемент
prev_node - предыдущий элемент
pop - метод удаления элемента из очереди
is_empty - метод проверки очереди на пустоту
highest_priority_node - элемент с наибольшим приоритетом
next_node - следующий элемент
peek - метод просмотра элемента с наивысшим приоритетом
size - метод получения размера очереди

class Node:
    def __init__(self, data=None, priority=None, next=None, prev=None):
        self.data = data
        self.priority = priority
        self.next = next
        self.prev = prev
        
class PriorityQueue:
    def __init__(self):
        self.head = Node(priority=float('inf'))
        self.tail = Node(priority=float('-inf'))

        self.head.next = self.tail
        self.tail.prev = self.head
        self._size = 0

    def push(self, data, priority):
        new_element = Node(data, priority)
        current = self.head.next
        
        while current.priority >= priority:
            current = current.next

        prev_node = current.prev
        new_element.next = current
        new_element.prev = prev_node
        prev_node.next = new_element
        current.prev = new_element
        self._size += 1

    def pop(self):
        if self.is_empty():
            raise IndexError("Попытка извлечения элемента из пустой очереди")

        highest_priority_node = self.head.next
        next_node = highest_priority_node.next
        self.head.next = next_node
        next_node.prev = self.head
        self._size -= 1

        return highest_priority_node.data

    def is_empty(self):
        return self.head.next == self.tail

    def peek(self):
        if self.is_empty():
            raise IndexError("Очередь пуста")
            
        return self.head.next.data

    def size(self):
        return self._size

---

Реализация на C++

Аннотация:
template - шаблон функции
Node - узел
data - данные, хранящиеся в узле
priority - приоритет узла
next - указатель на следующий элемент в очереди
prev - указатель на предыдущий элемент в очереди
new_data - новое значение узла
new_priority - новый приоритет узла
PriorityQueue - очередь с приоритетом
head - начало очереди
tail - конец очереди
_size - размер очереди
push - метод добавления элемента в очередь
new_element - добавляемый в очередь элемент
current - текущий элемент
prev_node - предыдущий элемент
pop - метод удаления элемента из очереди
is_empty - метод проверки очереди на пустоту
highest_priority_node - элемент с наибольшим приоритетом
next_node - следующий элемент
peek - метод просмотра элемента с наивысшим приоритетом
size - метод получения размера очереди

#include <iostream>
#include <stdexcept>

template <typename T>
struct Node {
    T data;
    int priority;
    Node* next;
    Node* prev;

    Node(T new_data = T(), int new_priority = 0) 
        : data(new_data), priority(new_priority), next(nullptr), prev(nullptr) {}
};

template <typename T>
class PriorityQueue {
private:
    Node<T>* head;
    Node<T>* tail;
    int _size;

public:
    PriorityQueue() {
        head = new Node<T>(T(), INT_MAX);
        tail = new Node<T>(T(), INT_MIN);

        head->next = tail;
        tail->prev = head;
        _size = 0;
    }

    ~PriorityQueue() {
        Node<T>* current = head;
        while (current != nullptr) {
            Node<T>* next_node = current->next;
            delete current;
            current = next_node;
        }
    }

    void push(T data, int priority) {
        Node<T>* new_element = new Node<T>(data, priority);

        Node<T>* current = head->next;
        while (current->priority >= priority) {
            current = current->next;
        }

        Node<T>* prev_node = current->prev;
        new_element->next = current;
        new_element->prev = prev_node;
        prev_node->next = new_element;
        current->prev = new_element;

        _size++;
    }

    T pop() {
        if (is_empty()) {
            throw std::out_of_range("Попытка извлечения элемента из пустой очереди");
        }

        Node<T>* highest_priority_node = head->next;

        Node<T>* next_node = highest_priority_node->next;
        head->next = next_node;
        next_node->prev = head;

        T data = highest_priority_node->data;
        delete highest_priority_node;
        _size--;

        return data;
    }

    bool is_empty() const {
        return head->next == tail;
    }

    T peek() const {
        if (is_empty()) {
            throw std::out_of_range("Очередь пуста");
        }
        return head->next->data;
    }

    int size() const {
        return _size;
    }
};