В этой статье я покажу очередь с приоритетом с использованием 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 и заполняю нулями указатели. Когда мы вставляем новое число с приоритетом, то оно сравнивается, есть ли такой приоритет, если есть, то мы попадаем сразу в конец этого приоритета и добавляем свой.
