Алгоритм. Очередь с приоритетом

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

Я сначала поискал в интернете реализацию такого алгоритма. Первое, что я нашел, это решение на c++ с обычными массивами. То есть создается шаблонный класс и в нем создается два массива, один для чисел, другой для приоритетности. Мне показалось, что решение не очень хорошее, потому что при добавлении нового числа, создается новый массив и из старого копируются данные в новый массив. Чем больше очередь, тем больше копирования каждый раз. Ещё проблема при использовании массива — это что нельзя использовать в другом потоке очередь, пока ты не выполнишь полностью функцию вставки данных в очередь, так как смениться указатель на массив и так далее.

Алгоритм — очередь с приоритетом достаточно простой, мы создаем структуру, я опять буду показывать пример кода на C, и входящие данные будут числа. Итак.

struct queue { unsigned long number; unsigned long priority; struct queue *parent; struct queue *child; };

Также создаем глобальный указатель на начало очереди, прошу заметить, это всего лишь пример, разумеется в C++ можно создать это в классе, но так как в C будет только одна очередь, то она становиться глобальной как само собой разумеющееся. И также создаем pri указатель на указатель. Он будет хранить хвост каждого приоритета, чтобы можно было в linked-list сразу в нужное место всегда добавлять новые данные.

struct queue *root; struct queue **pri;

теперь создаем функцию и начальные значения. Здесь мы также ищем близжайший приоритет. например если у нас первым был приоритет 20, потом 14, а теперь 10. то мы линейно доходим до 14 и становимся в его хвост и добавляемся уже рядом с ним.

static void add_number (int number, int priority, int max) { register struct queue *n = root; register struct queue *prev = NULL; register struct queue *temp = NULL; register struct queue *temp1 = NULL; int prr = priority + 20; while ((n = pri[prr]) == NULL)  {  prr++;  if (prr >= max) break; }   if (n == NULL) n = root;

Теперь можно в бесконечном цикле идти по списку и добавлять в нужную позицию наше число. Начнем с того, если указатель n равен нулю.

if (n == NULL) { n = calloc (1, sizeof (struct queue)); n->number = number; n->priority = priority; if (prev) { prev->child = n; n->parent = prev; } pri[priority + 20] = n; if (root == NULL) root = n; return; }

Здесь в указываем чтобы root указывал на него как на начало. Отсюда начнется следующий отсчет.

Далее мы смотрим, если добавляемый приоритет выше, чем наше сообщение в очереди, то перед ним установим новый приоритет.

while (n->priority < priority) { temp = n; prev = n; n = n->parent; if (n == NULL) { n = calloc (1, sizeof (struct queue)); n->number = number; n->priority = priority; n->child = temp; temp->parent = n; root = n; pri[priority + 20] = n; return; } }

Также можно заметить, что в этом случае root опять меняет свою позицию, указав себя как начало в списке.

Далее смотрим если добавляемый приоритет ниже чем текущий приоритет.

while (n->priority > priority)  { temp = n; prev = n; n = n->child; if (n == NULL) { n = calloc (1, sizeof (struct queue)); n->number = number; n->priority = priority; n->parent = temp; temp->child = n; pri[priority + 20] = n; return; } else if (n->priority <= priority) { temp = n->parent; temp1 = n; n = calloc (1, sizeof (struct queue)); n->number = number; n->priority = priority; n->parent = temp; n->child = temp1; temp->child = n; temp1->parent = n; pri[priority + 20] = n; return; } }

Здесь всё должно быть понятно, что мы добавляем наше число куда нужно.

И осталось последнее.

while (n->priority == priority) { temp = n; prev = n; n = n->child; if (n == NULL) { n = calloc (1, sizeof (struct queue)); n->number = number; n->priority = priority; n->child = NULL; n->parent = n; temp->child = n; pri[priority + 20] = n; return; } else if (n->priority != priority) { temp = n->parent; temp1 = n; n = calloc (1, sizeof (struct queue)); n->number = number; n->priority = priority; n->parent = temp; n->child = temp1; pri[priority + 20] = n; return; } }

Здесь мы смотрим, если он равен нашему приоритету, то дадим сначала выйти из очереди первому добавленному с таким приоритетом, а этот добавим за ним.

Теперь создадим функцию по выдачи из очереди нашего числа.

static int get_number_from_queue () { if (!root) return -1; register struct queue *n = root; root = root->child; register unsigned long number = n->number; free (n); return number; }

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

Теперь создадим остальное.

struct arr { int num; int priority; } arr[] = { { -14, -14}, { -4, -4}, { 0, 0 }, { 1, 1 }, { 2, 2 }, { 3, 3 }, { 4, 4 }, { 14, 14 }, { 5, 5 }, { 5, 5 }, { 6, 6 }, { 7, 7 }, { 8, 8 }, { 9, 9 }, { 10, 10 } };  int main (int argc, char **argv) { pri = calloc (41, sizeof (struct queue *)); for (int i = 0; i < 41; i++) { pri[i] = NULL; }  int size = sizeof (arr) / sizeof (struct arr); for (int i = 0; i < size; i++) { add_number (arr[i].num, arr[i].priority); }  for (int i = 0; i < size; i++) { printf ("%d: %d\n", i, get_number_from_queue()); } }

Чтобы было удобней проверить код, то выкладываю полный код.

#include <stdio.h> #include <unistd.h> #include <stdlib.h>  struct queue { unsigned long number; long priority; struct queue *parent; struct queue *child; };  struct queue *root; struct queue **pri;  static void add_number (int number, int priority) { register struct queue *n = root; register struct queue *prev = NULL; register struct queue *temp = NULL; register struct queue *temp1 = NULL; int prr = priority + 20; while ((n = pri[prr]) == NULL)  {  prr++;  if (prr >= max) break; }   if (n == NULL) n = root; while (1) { if (n == NULL) { n = calloc (1, sizeof (struct queue)); n->number = number; n->priority = priority; if (prev) { prev->child = n; n->parent = prev; } pri[priority + 20] = n; if (root == NULL) root = n; return; } while (n->priority < priority) { temp = n; prev = n; n = n->parent; if (n == NULL) { n = calloc (1, sizeof (struct queue)); n->number = number; n->priority = priority; n->child = temp; temp->parent = n; root = n; pri[priority + 20] = n; return; } } while (n->priority > priority)  { temp = n; prev = n; n = n->child; if (n == NULL) { n = calloc (1, sizeof (struct queue)); n->number = number; n->priority = priority; n->parent = temp; temp->child = n; pri[priority + 20] = n; return; } else if (n->priority <= priority) { temp = n->parent; temp1 = n; n = calloc (1, sizeof (struct queue)); n->number = number; n->priority = priority; n->parent = temp; n->child = temp1; temp->child = n; temp1->parent = n; pri[priority + 20] = n; return; } } while (n->priority == priority) { temp = n; prev = n; n = n->child; if (n == NULL) { n = calloc (1, sizeof (struct queue)); n->number = number; n->priority = priority; n->child = NULL; n->parent = n; temp->child = n; pri[priority + 20] = n; return; } else if (n->priority != priority) { temp = n->parent; temp1 = n; n = calloc (1, sizeof (struct queue)); n->number = number; n->priority = priority; n->parent = temp; n->child = temp1; pri[priority + 20] = n; return; } } } }  static int get_number_from_queue () { if (!root) return -1; register struct queue *n = root; root = root->child; register unsigned long number = n->number; free (n); return number; }  struct arr { int num; int priority; } arr[] = { { -14, -14}, { -4, -4}, { 0, 0 }, { 1, 1 }, { 2, 2 }, { 3, 3 }, { 4, 4 }, { 14, 14 }, { 5, 5 }, { 5, 5 }, { 6, 6 }, { 7, 7 }, { 8, 8 }, { 9, 9 }, { 10, 10 } };  int main (int argc, char **argv) { pri = calloc (41, sizeof (struct queue *)); for (int i = 0; i < 41; i++) { pri[i] = NULL; }  int size = sizeof (arr) / sizeof (struct arr); for (int i = 0; i < size; i++) { add_number (arr[i].num, arr[i].priority); }  for (int i = 0; i < size; i++) { printf ("%d: %d\n", i, get_number_from_queue()); } }

разумеется надо знать какие приоритеты доступны, то есть например я выбираю, что доступны приоритеты от -20 до 20. создаю массив pri и заполняю нулями указатели. Когда мы вставляем новое число с приоритетом, то оно сравнивается, есть ли такой приоритет, если есть, то мы попадаем сразу в конец этого приоритета и добавляем свой.