Приоритетная очередь в структуре данных: характеристики, типы и реализация

Опубликовано: 2021-05-02

Оглавление

Введение

Приоритетная очередь в структуре данных является расширением «обычной» очереди. Это абстрактный тип данных, который содержит группу элементов. Это похоже на «нормальную» очередь, за исключением того, что исключаемые из очереди элементы следуют порядку приоритета. Порядок приоритета удаляет из очереди те элементы, которые имеют наивысший приоритет. Этот блог даст вам более глубокое понимание очереди приоритетов и ее реализации на языке программирования C.

Что такое приоритетная очередь?

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

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

Вы можете думать об очереди с приоритетом как о нескольких пациентах, стоящих в очереди в больнице. Здесь положение пациента определяет порядок приоритета. Пациент с наиболее тяжелой травмой будет первым в очереди.

Каковы характеристики приоритетной очереди?

Очередь называется очередью с приоритетом, если она имеет следующие характеристики:

  • Каждый элемент имеет определенный приоритет, связанный с ним.
  • Элемент с наивысшим приоритетом перемещается вперед и удаляется первым.
  • Если два элемента имеют одинаковое значение приоритета, то приоритетная очередь следует принципу «первым пришел — первым обслужен» при работе с очередью.

Какие существуют типы приоритетной очереди?

Приоритетная очередь бывает двух типов:

  • Приоритетная очередь по возрастанию
  • Приоритетная очередь по убыванию

Приоритетная очередь по возрастанию

Очередь с возрастающим приоритетом дает наивысший приоритет меньшему номеру в этой очереди. Например, у вас есть шесть номеров в приоритетной очереди: 4, 8, 12, 45, 35, 20. Во-первых, вы расположите эти числа в порядке возрастания. Новый список выглядит следующим образом: 4, 8, 12, 20. 35, 45. В этом списке 4 — наименьшее число. Следовательно, очередь с возрастающим приоритетом рассматривает номер 4 как наивысший приоритет.

4 8 12 20 35 45

В приведенной выше таблице 4 имеет самый высокий приоритет, а 45 — самый низкий.

Приоритетная очередь по убыванию

Очередь с убывающим приоритетом дает наивысший приоритет самому высокому номеру в этой очереди. Например, у вас есть шесть номеров в приоритетной очереди: 4, 8, 12, 45, 35, 20. Во-первых, вы расположите эти числа в порядке возрастания. Новый список выглядит следующим образом: 45, 35, 20, 12, 8, 4. В этом списке 45 — самое большое число. Следовательно, очередь с убывающим приоритетом рассматривает номер 45 как наивысший приоритет.

45 35 20 12 8 4

В приведенной выше таблице 4 имеет самый низкий приоритет, а 45 — самый высокий.

Реализация приоритетной очереди в структуре данных

Вы можете реализовать приоритетные очереди одним из следующих способов:

  • Связанный список
  • Двоичная куча
  • Массивы
  • Бинарное дерево поиска

Двоичная куча — наиболее эффективный метод реализации приоритетной очереди в структуре данных .

В приведенных ниже таблицах обобщена сложность различных операций в очереди с приоритетом.

Операция Неупорядоченный массив Упорядоченный массив Двоичная куча Бинарное дерево поиска
Вставлять 0(1) 0(Н) 0 (журнал (N)) 0 (журнал (N))
заглянуть 0(Н) 0(1) 0(1) 0(1)
Удалить 0(Н) 0(1) 0 (логарифм (N)) 0 (журнал (N))

Двоичная куча

Двоичное дерево кучи организует все родительские и дочерние узлы дерева в определенном порядке. В двоичном дереве кучи родительский узел может иметь максимум 2 дочерних узла. Значение родительского узла может быть:

  • равно или меньше значения дочернего узла.
  • равно или больше, чем значение дочернего узла.

Описанный выше процесс делит двоичную кучу на два типа: максимальная куча и минимальная куча.

Макс куча

Максимальная куча — это двоичная куча, в которой родительский узел имеет значение, равное или превышающее значение дочернего узла. Корневой узел дерева имеет наибольшее значение.

Вставка элемента в двоичное дерево с максимальной кучей

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

  1. Алгоритм сканирует дерево сверху вниз и слева направо, чтобы найти пустой слот. Затем он вставляет элемент в последний узел дерева.
  2. После вставки элемента порядок бинарного дерева нарушается. Вы должны поменять местами данные друг с другом, чтобы отсортировать порядок двоичного дерева максимальной кучи. Вы должны перетасовывать данные до тех пор, пока дерево не будет удовлетворять свойству max-heap.

Алгоритм вставки элемента в двоичное дерево с максимальной кучей

Если дерево пусто и не содержит узлов,

создайте новый родительский узел newElement.

иначе (родительский узел уже доступен)

вставьте новый элемент в конец дерева (т. е. последний узел дерева слева направо).

max-heapify дерево

Удаление элемента в двоичном дереве с максимальной кучей

  1. Вы можете выполнить следующие шаги, чтобы удалить элемент в очереди приоритетов в структуре данных .
  2. Выберите элемент, который вы хотите удалить из двоичного дерева.
  3. Сдвиньте данные в конце дерева, заменив их данными последнего узла.
  4. Удалить последний элемент бинарного дерева.
  5. После удаления элемента порядок бинарного дерева нарушается. Вы должны отсортировать порядок, чтобы удовлетворить свойству max-heap. Вы должны перетасовывать данные до тех пор, пока дерево не будет соответствовать свойству max-heap.

Алгоритм удаления элемента в двоичном дереве с максимальной кучей

Если elementUpForDeletion является последним узлом,

удалить элементUpForDeletion

иначе замените elementUpForDeletion на lastNode

удалить элементUpForDeletion

max-heapify дерево

Найдите максимальный или минимальный элемент в двоичном дереве с максимальной кучей

В двоичном дереве с максимальной кучей операция поиска возвращает родительский узел (самый высокий элемент) дерева.

Алгоритм поиска максимума или минимума в двоичном дереве с максимальной кучей

вернуть родительский узел

Программная реализация очереди приоритетов с использованием двоичного дерева Max Heap

#include <stdio.h>

интервал двоичного_дерева = 10;

интервал max_heap = 0;

константа int test = 100000;

недействительный обмен (int * x, int * y) {

в а;

а = *х;

*х= *у;

*у = а;

}

//Код для поиска родителя в дереве максимальной кучи

int findParentNode (int node [], int root) {

если ((корень > 1) && (корень < двоичное_дерево)) {

вернуть корень/2;

}

возврат -1;

}

недействительным max_heapify (int node [], int root) {

int leftNodeRoot = findLeftChild (узел, корень);

int rightNodeRoot = findRightChild (узел, корень);

// поиск наибольшего среди корня, левого потомка и правого потомка

интервал наивысший = корень;

if ((leftNodeRoot <= max_heap) && (leftNodeRoot >0)) {

если (узел [leftNodeRoot] > узел [самый высокий]) {

самый высокий = левыйNodeRoot;

}

}

if ((rightNodeRoot <= max_heap) && (rightNodeRoot >0)) {

если (узел[правыйNodeRoot] > узел[самый высокий]) {

наивысший = правый корень узла;

}

}

если (самый высокий != корень) {

swap(&узел[корень], &узел[самый высокий]);

max_heapify (узел, самый высокий);

}

}

недействительным create_max_heap (целый узел []) {

инт д;

for(d=max_heap/2; d>=1; d–) {

max_heapify (узел, д);

}

}

интервал максимум (целый узел []) {

вернуть узел[1];

}

интервал find_max (целый узел []) {

int maxNode = узел[1];

узел[1] = узел[max_heap];

макс_куча–;

max_heapify (узел, 1);

вернуть максимальный узел;

}

недействительными спускаемый_ключ (целый узел [], целочисленный узел, целочисленный ключ) {

A[корень] = ключ;

max_heapify (узел, корень);

}

недействительное увеличение_ключа (целый узел [], корень целого числа, ключ целого числа) {

узел[корень] = ключ;

в то время как ((корень> 1) && (узел [findParentNode (узел, корень)] < узел [корень])) {

swap(&node[root], &node[findParentNode(node, root)]);

корень = findParentNode (узел, корень);

}

}

пустая вставка (целый узел [], целочисленный ключ) {

макс_куча++;

узел[max_heap] = -1*тест;

увеличить_ключ (узел, максимальная_куча, ключ);

}

недействительным display_heap (целый узел []) {

инт д;

for(d=1; d<=max_heap; d++) {

printf("%d\n",узел[d]);

}

printf("\n");

}

интервал основной () {

целый узел[бинарное_дерево];

вставить (узел, 10);

вставить (узел, 4);

вставить (узел, 20);

вставить (узел, 50);

вставить (узел, 1);

вставить (узел, 15);

display_heap (узел);

printf("%d\n\n", максимум(узел));

display_heap (узел);

printf("%d\n", extract_max(узел));

printf("%d\n", extract_max(узел));

вернуть 0;

}

Минимальная куча

Минимальная куча — это двоичная куча, в которой родительский узел имеет значение, равное или меньшее, чем значение дочернего узла. Корневой узел дерева имеет наименьшее значение.

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

Заключение

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

Если вам интересно узнать о науке о данных, ознакомьтесь с программой IIIT-B & upGrad Executive PG по науке о данных, которая создана для работающих профессионалов и предлагает более 10 тематических исследований и проектов, практические семинары, наставничество с отраслевыми экспертами, 1 -на-1 с отраслевыми наставниками, более 400 часов обучения и помощи в трудоустройстве в ведущих фирмах.

Изучайте онлайн- курсы по науке о данных в лучших университетах мира. Участвуйте в программах Executive PG, Advanced Certificate Programs или Master Programs, чтобы ускорить свою карьеру.

Каковы приложения приоритетной очереди?

Очередь с приоритетом — это специальная очередь, в которую элементы вставляются в зависимости от их приоритета. Эта функция оказывается полезной при реализации различных других структур данных. Ниже приведены некоторые из наиболее популярных приложений приоритетной очереди:
 1. Алгоритм кратчайшего пути Дейкстры: Очередь с приоритетами может использоваться в алгоритме кратчайшего пути Дейкстры, когда граф хранится в виде списка смежности.
 2. Алгоритм Прима : Алгоритм Прима использует приоритетную очередь для значений или ключей узлов и извлекает минимум этих значений на каждом шаге.
 Сжатие данных : коды Хаффмана используют приоритетную очередь для сжатия данных.
 Операционные системы: очередь с приоритетами очень полезна для операционных систем в различных процессах, таких как балансировка нагрузки и обработка прерываний.

Какой подход используется при реализации приоритетной очереди с использованием массива?

Подход, используемый при реализации приоритетной очереди с использованием массива, прост. Структура создается для хранения значений и приоритета элемента, а затем создается массив этой структуры для хранения элементов. В этой реализации участвуют следующие операции:
 1. enqueue() — эта функция вставляет элементы в конец очереди.
 2. peek() — эта функция будет проходить по массиву, чтобы вернуть элемент с наивысшим приоритетом. Если он находит два элемента с одинаковым приоритетом, он возвращает элемент с наибольшим значением среди них.
 3. dequeue() — эта функция сдвинет все элементы на 1 позицию влево от элемента, возвращаемого функцией peek(), и уменьшит размер.

В чем разница между максимальной кучей и минимальной кучей?

Ниже показано различие между максимальной кучей и минимальной кучей.
 Минимальная куча — в минимальной куче ключ корневого узла должен быть меньше или равен ключам его дочернего узла. Он использует восходящий приоритет. Узел с наименьшим ключом является приоритетным. Наименьший элемент выталкивается перед любым другим элементом.
 Максимальная куча . В максимальной куче ключ корневого узла должен быть больше или равен ключу его дочерних узлов. Он использует нисходящий приоритет. Узел с наибольшим ключом является приоритетным. Самый большой элемент выталкивается перед любым другим элементом.