Что такое приоритетная очередь
Очередь (queue) в C++: легко и просто!
Всем привет! Для решения задач многие программисты используют структуру данных — очередь. Вы наверно когда-то слышали о ней, а возможно и применяли в своей программе.
Мы попытаемся ответить на несколько вопросов: что такое очередь, принцип работы очереди и какая у нее есть разновидность. Поехали!
Что такое очередь
В очереди, если вы добавите элемент, который вошел самый первый, то он выйдет тоже самым первым. Получается, если вы добавите 4 элемента, то первый добавленный элемент выйдет первым.
Чтобы понять принцип работы очереди вы можете представить себе магазинную очередь. И вы стоите посреди нее, чтобы вы оказались напротив кассы, сначала понадобится всех впереди стоящих людей обслужить. А вот для последнего человека в очереди нужно, чтобы кассир обслужил всех людей кроме него самого.
На рисунке слева находятся 7 чисел: 2, 4, 7, 1, 4, 9, 10. Если нам понадобится их извлечь, то извлекать мы будем в таком же порядке как они находятся на рисунке!
Так например чтобы извлечь число 4 нам понадобится сначала обслужить число 2, а потом уже и само число 4.
Хотя в стеке присутствует функция peek() (она позволяет обратится к элементу по индексу, подробнее вот здесь), в шаблоне очереди невозможно обратится к определенному элементу.
Но если вам нужно иметь доступ ко всем элементам очереди, то можете реализовать очередь через массив. Чуть ниже мы покажем как это сделать.
Как создать очередь в С++
Дальше для объявления очереди нужно воспользоваться конструкцией ниже.
Алгоритм. Очередь с приоритетом
В этой статье я покажу очередь с приоритетом с использованием linked list. Алгоритм простой и позволяет получить приоритетные сообщения раньше, чем остальные сообщения.
Также создаем глобальный указатель на начало очереди, прошу заметить, это всего лишь пример, разумеется в C++ можно создать это в классе, но так как в C будет только одна очередь, то она становиться глобальной как само собой разумеющееся. И также создаем pri указатель на указатель. Он будет хранить хвост каждого приоритета, чтобы можно было в linked-list сразу в нужное место всегда добавлять новые данные.
теперь создаем функцию и начальные значения. Здесь мы также ищем близжайший приоритет. например если у нас первым был приоритет 20, потом 14, а теперь 10. то мы линейно доходим до 14 и становимся в его хвост и добавляемся уже рядом с ним.
Теперь можно в бесконечном цикле идти по списку и добавлять в нужную позицию наше число. Начнем с того, если указатель n равен нулю.
Здесь в указываем чтобы root указывал на него как на начало. Отсюда начнется следующий отсчет.
Далее мы смотрим, если добавляемый приоритет выше, чем наше сообщение в очереди, то перед ним установим новый приоритет.
Также можно заметить, что в этом случае root опять меняет свою позицию, указав себя как начало в списке.
Далее смотрим если добавляемый приоритет ниже чем текущий приоритет.
Здесь всё должно быть понятно, что мы добавляем наше число куда нужно.
И осталось последнее.
Здесь мы смотрим, если он равен нашему приоритету, то дадим сначала выйти из очереди первому добавленному с таким приоритетом, а этот добавим за ним.
Теперь создадим функцию по выдачи из очереди нашего числа.
Всё, здесь мы выдаем номер и смещаем наш root. Так как это без много поточности, то здесь я не использовал мьютексы, но по хорошему, нужно поставить мьютекс на смену root и всё.
Теперь создадим остальное.
Чтобы было удобней проверить код, то выкладываю полный код.
Очередь с приоритетом
В этой статье вы познакомитесь с очередями с приоритетом и узнаете, как их реализовать в Python, Java, C и C++.
Очереди с приоритетом — разновидность очередей, в которой у каждого элемента есть свой приоритет. Обслуживаются они в соответствии со своими приоритетом. Если у элементов одинаковый приоритет, то обслуживаются они по их порядку в очереди.
Значение элемента, как правило, и определяет его приоритет.
То есть, у элемента с самым большим значением самый высокий приоритет. Правда, это не всегда так. Самый высокий приоритет может быть у элемента и с самым малым значением. В остальных случаях мы можем задавать приоритеты элементам по своему усмотрению.
Разница между очередью с приоритетом и обычной очередью
Обычная очередь подчиняется принципу FIFO «первый вошел — первый вышел». В очередях с приоритетом элементы удаляются в соответствии с их приоритетом. То есть, элемент с самым высоким приоритетом удаляется из очереди в первую очередь.
Реализация очереди с приоритетом
Очереди с приоритетом можно реализовать с помощью следующих структур данных: массив, связный список, куча и двоичное дерево поиска. Среди всех этих структур выделяется куча — это самый эффективный способ реализации очереди с приоритетом.мы
Именно поэтому в этом руководстве мы будем использовать кучи. Конкретно — max-кучи.
Ниже представлена сравнительная характеристика различных реализаций очередей с приоритетом.
СОДЕРЖАНИЕ
Операции
Очередь с приоритетом должна поддерживать как минимум следующие операции:
Реализация
Наивные реализации
Существует множество простых, обычно неэффективных способов реализации очереди с приоритетами. Они предоставляют аналогию, чтобы помочь понять, что такое приоритетная очередь.
Например, можно сохранить все элементы в несортированном списке ( время вставки O (1)). Всякий раз, когда запрашивается элемент с наивысшим приоритетом, ищите среди всех элементов элемент с наивысшим приоритетом. ( O ( n ) время вытягивания),
В другом случае можно сохранить все элементы в списке с сортировкой по приоритету ( время сортировки вставки O (n)), всякий раз, когда запрашивается элемент с наивысшим приоритетом, может быть возвращен первый в списке. ( O (1) время вытягивания)
Обычная реализация
С точки зрения вычислительной сложности очереди с приоритетами соответствуют алгоритмам сортировки. В разделе об эквивалентности очередей приоритетов и алгоритмов сортировки ниже описывается, как эффективные алгоритмы сортировки могут создавать эффективные очереди приоритетов.
Специализированные отвалы
Для приложений, которые выполняют множество операций « просмотра » для каждой операции «extract-min», временная сложность действий просмотра может быть уменьшена до O (1) во всех реализациях дерева и кучи путем кэширования элемента с наивысшим приоритетом после каждой вставки и удаления. Для вставки это добавляет максимум постоянную стоимость, поскольку вновь вставленный элемент сравнивается только с ранее кэшированным минимальным элементом. Для удаления это не более чем добавляет дополнительные затраты на «просмотр», которые обычно дешевле, чем затраты на удаление, поэтому общая временная сложность существенно не влияет.
Сводка времени работы
| Операция | find-min | delete-min | вставлять | клавиша уменьшения | объединить |
|---|---|---|---|---|---|
| Двоичный | Θ (1) | Θ (журнал n ) | O (журнал n ) | O (журнал n ) | Θ ( п ) |
| Левый | Θ (1) | Θ (журнал n ) | Θ (журнал n ) | O (журнал n ) | Θ (журнал n ) |
| Биномиальный | Θ (1) | Θ (журнал n ) | Θ (1) | Θ (журнал n ) | O (журнал n ) |
| Фибоначчи | Θ (1) | O (журнал n ) | Θ (1) | Θ (1) | Θ (1) |
| Сопряжение | Θ (1) | O (журнал n ) | Θ (1) | o (войти n ) | Θ (1) |
| Brodal | Θ (1) | O (журнал n ) | Θ (1) | Θ (1) | Θ (1) |
| Ранговые пары | Θ (1) | O (журнал n ) | Θ (1) | Θ (1) | Θ (1) |
| Строгий Фибоначчи | Θ (1) | O (журнал n ) | Θ (1) | Θ (1) | Θ (1) |
| 2–3 кучи | O (журнал n ) | O (журнал n ) | O (журнал n ) | Θ (1) | ? |
Эквивалентность приоритетных очередей и алгоритмов сортировки
Использование очереди приоритетов для сортировки
В Семантике приоритетных очередей естественно предложить метод сортировки: вставить все элементы должны быть отсортированы в приоритетную очередь, и последовательно удалить их; они появятся в отсортированном порядке. Фактически это процедура, используемая несколькими алгоритмами сортировки после удаления уровня абстракции, обеспечиваемого очередью приоритетов. Этот метод сортировки эквивалентен следующим алгоритмам сортировки:
Использование алгоритма сортировки для создания очереди с приоритетом
Алгоритм сортировки также может использоваться для реализации очереди с приоритетами. В частности, Торуп говорит:
Мы представляем общее детерминированное линейное сокращение пространства от приоритетных очередей до сортировки, подразумевая, что если мы можем отсортировать до n ключей за S ( n ) раз на каждый ключ, тогда будет приоритетная очередь, поддерживающая удаление и вставку в O ( S ( n )) time и find-min в постоянное время.
Библиотеки
Очередь с приоритетом часто считается « структурой данных контейнера ».
Модуль Python heapq реализует двоичную минимальную кучу поверх списка.
Библиотека Java содержит PriorityQueue класс, который реализует очередь с минимальным приоритетом.
Приложения
Управление пропускной способностью
Дискретное моделирование событий
Алгоритм Дейкстры
Кодирование Хаффмана
Алгоритмы поиска лучшего первого
Алгоритм триангуляции ROAM
Алгоритм оптимальной адаптации сетки в реальном времени ( ROAM ) вычисляет динамически изменяющуюся триангуляцию местности. Он работает, разделяя треугольники там, где требуется больше деталей, и объединяя их там, где требуется меньше деталей. Алгоритм назначает каждому треугольнику на местности приоритет, обычно связанный с уменьшением ошибки, если этот треугольник будет разделен. Алгоритм использует две приоритетные очереди: одну для треугольников, которые можно разделить, а другую для треугольников, которые можно объединить. На каждом шаге треугольник из очереди разделения с наивысшим приоритетом разделяется, или треугольник из очереди слияния с самым низким приоритетом объединяется со своими соседями.
Алгоритм Прима для минимального остовного дерева
Очередь с параллельным приоритетом
Параллельный параллельный доступ
Если приоритетная очередь разрешает одновременный доступ, несколько процессов могут одновременно выполнять операции с этой приоритетной очередью. Однако здесь возникают две проблемы. Во-первых, определение семантики отдельных операций перестало быть очевидным. Например, если два процесса хотят извлечь элемент с наивысшим приоритетом, должны ли они получить один и тот же элемент или разные? Это ограничивает параллелизм на уровне программы, использующей очередь приоритетов. Кроме того, поскольку несколько процессов имеют доступ к одному и тому же элементу, это приводит к конфликту.
Если разрешен одновременный доступ к приоритетной очереди, между двумя процессами могут возникнуть конфликты. Например, конфликт возникает, если один процесс пытается вставить новый узел, но в то же время другой процесс собирается удалить предшественника этого узла. Существует риск того, что новый узел будет добавлен в список пропуска, но недоступен. ( См. Изображение )
K-элементные операции
В оставшейся части этого раздела обсуждается алгоритм распределенной памяти на основе очередей. Мы предполагаем, что каждый процессор имеет свою собственную локальную память и локальную (последовательную) очередь приоритетов. Элементы очереди с глобальным (параллельным) приоритетом распределяются по всем процессорам.
Русские Блоги
Очередь приоритетов PHP
Очередь приоритетов PHP
1. Что такое приоритетная очередь?
В стадии разработки находится множество приложений очередей. Наиболее широко используются очереди сообщений, которые используются для обработки некоторых задач, таких как размещение заказов и срочные покупки. Их необходимо отсортировать по времени запроса. Первое приходит первым. Ключевым моментом является поддержание последовательной структуры. В реальной разработке мы обычно редко реализуем очередь самостоятельно и обычно используем некоторые готовые службы, такие как redis queue и rabbitmq.
Priority Queue, как следует из названия, представляет собой очередь с приоритетом, что означает, что она сортируется не в порядке запросов, а также в соответствии с определенными атрибутами правил. Например: существует около 12306 программ для считывания билетов, и шанс получить билет выше, если вы потратите деньги на пакет ускорения. Так называемая более высокая вероятность здесь имеет более высокий приоритет: если билетов всего 10, он должен первым получить билеты для тех, кто потратил деньги, а те, кто не потратил деньги, окажутся позади.
2. Зачем нужна приоритетная очередь?
Если предположить, что билеты получают 10 000 человек, 50 из них заплатили разные суммы денег.Когда система получает билет, его необходимо распределить в порядке убывания в соответствии с количеством оплаченных пользователей. Если бы вас попросили реализовать упомянутый выше приоритет получения билетов, как бы вы его разработали?
Практика первая:
Метод второй:
Для достижения используйте отсортированный набор Redis, отсортированный набор Redis также является набором элементов строкового типа, таких как набор, и дублирование элементов не допускается. Разница в том, что каждый элемент связан с оценкой двойного типа. Redis использует оценки для сортировки членов коллекции от мала до велика. Члены упорядоченной коллекции уникальны, но оценка (оценка) может повторяться.
Практика третья:
Используя очереди приоритетов, большинство языков программирования имеют собственную реализацию очереди приоритетов в стандартной библиотеке, и вам не нужно реализовывать ее самостоятельно. Однако веб-программы, такие как PHP, будут уничтожать данные в памяти после каждого запроса. Используйте очередь приоритетов, созданную вами. Это не так хорошо, как второй подход или реализация резидентной службы процесса для веб-вызовов.
3. Принцип и использование
Есть две двоичные кучи: самая большая и самая маленькая. Максимальная куча: значение ключа родительского узла всегда больше или равно значению ключа любого дочернего узла; минимальная куча: значение ключа родительского узла всегда меньше или равно значению ключа любого дочернего узла.
Вышеупомянутое содержание предназначено только для справки. Реализация и детали алгоритма этих структур данных здесь не упоминаются. В конце концов, это непросто. Если вам интересно, вы можете узнать об этом больше.
Хотя эти алгоритмы не просты, в конце концов, мы все стоим на плечах гигантов.Давайте посмотрим на реализацию приоритетных очередей, предусмотренную в PHP SPL. Стандартная библиотека PHP предоставляет часто используемые структуры данных, такие как связанный список, куча, стек, максимальная куча, минимальная куча и массив фиксированного размера. Среди них есть очередь с приоритетом. Краткое описание класса выглядит следующим образом:
Среди них обычно используются методы compare, count, current, insert, next, rewind, valid и другие. Использование относительно простое. Давайте рассмотрим полный пример ниже:
По умолчанию это сортируется по числовому значению, но что, если сравниваемый атрибут не является числовым значением? Например, это объект. На данный момент мы можем использовать следующую формулировку. Мы можем создать новый класс, который наследует класс стандартной библиотеки, а затем переписать метод сравнения в соответствии с нашими собственными правилами:
Вы понимаете? Пожалуйста, поправьте меня, если это не так!