Kolejka priorytetów w strukturze danych: cechy, typy i implementacja

Opublikowany: 2021-05-02

Spis treści

Wstęp

Kolejka priorytetowa w strukturze danych jest rozszerzeniem kolejki „normalnej”. Jest to abstrakcyjny typ danych, który zawiera grupę elementów. Przypomina to „normalną” kolejkę, z tą różnicą, że elementy usuwające kolejkę są zgodne z kolejnością priorytetów. Kolejność priorytetu usuwa z kolejki te elementy, które mają najwyższy priorytet. Ten blog pozwoli ci lepiej zrozumieć kolejkę priorytetów i jej implementację w języku programowania C.

Co to jest kolejka priorytetowa?

Jest to abstrakcyjny typ danych, który zapewnia sposób na utrzymanie zestawu danych. „Normalna” kolejka przebiega według wzorca „pierwsze weszło-pierwsze wyszło”. Wycofuje elementy z kolejki w tej samej kolejności, co podczas operacji wstawiania. Jednak kolejność elementów w kolejce priorytetowej zależy od priorytetu elementu w tej kolejce. Kolejka priorytetowa przenosi elementy o najwyższym priorytecie na początek kolejki priorytetowej i elementy o najniższym priorytecie na tył kolejki priorytetowej.

Obsługuje tylko te elementy, które są porównywalne. W związku z tym kolejka priorytetowa w strukturze danych porządkuje elementy w kolejności rosnącej lub malejącej.

Możesz myśleć o kolejce priorytetowej jako o kilku pacjentach czekających w kolejce w szpitalu. Tutaj sytuacja pacjenta określa kolejność priorytetów. Pacjent z najcięższymi obrażeniami byłby pierwszy w kolejce.

Jakie są cechy kolejki priorytetowej?

Kolejka jest określana jako kolejka priorytetowa, jeśli ma następujące cechy:

  • Z każdym elementem związany jest jakiś priorytet.
  • Element o najwyższym priorytecie jest przesuwany z przodu i usuwany jako pierwszy.
  • Jeśli dwa elementy mają tę samą wartość priorytetu, kolejka priorytetowa jest zgodna z zasadą „pierwsze weszło-pierwsze wyszło” dla operacji usuwania kolejki.

Jakie są rodzaje kolejek priorytetowych?

Kolejka priorytetowa jest dwojakiego rodzaju:

  • Rosnąca kolejka priorytetów kolejności
  • Malejąca kolejka priorytetów kolejności

Rosnąca kolejka priorytetów kolejności

Kolejka priorytetu rosnącego nadaje najwyższy priorytet niższemu numerowi w tej kolejce. Na przykład masz sześć numerów w kolejce priorytetowej, czyli 4, 8, 12, 45, 35, 20. Najpierw ułożysz te numery w kolejności rosnącej. Nowa lista wygląda następująco: 4, 8, 12, 20. 35, 45. Na tej liście 4 to najmniejsza liczba. Stąd kolejka priorytetu rosnącego traktuje numer 4 jako najwyższy priorytet.

4 8 12 20 35 45

W powyższej tabeli 4 ma najwyższy priorytet, a 45 najniższy.

Malejąca kolejka priorytetów kolejności

Kolejka z malejącym priorytetem kolejności nadaje najwyższy priorytet najwyższej liczbie w tej kolejce. Na przykład masz sześć numerów w kolejce priorytetowej, czyli 4, 8, 12, 45, 35, 20. Najpierw ułożysz te numery w kolejności rosnącej. Nowa lista wygląda następująco: 45, 35, 20, 12, 8, 4. Na tej liście 45 jest najwyższą liczbą. Stąd kolejka malejącego priorytetu kolejności traktuje numer 45 jako najwyższy priorytet.

45 35 20 12 8 4

W powyższej tabeli 4 ma najniższy priorytet, a 45 najwyższy.

Implementacja kolejki priorytetów w strukturze danych

Kolejki priorytetowe można zaimplementować na jeden z następujących sposobów:

  • Połączona lista
  • Sterta binarna
  • Tablice
  • Drzewo wyszukiwania binarnego

Sterta binarna jest najbardziej efektywną metodą implementacji kolejki priorytetowej w strukturze danych .

Poniższe tabele podsumowują złożoność różnych operacji w kolejce priorytetowej.

Operacja Nieuporządkowana tablica Zamówiona tablica Sterta binarna Drzewo wyszukiwania binarnego
Wstawić 0(1) 0(N) 0(log(N)) 0(log(N))
Zerkać 0(N) 0(1) 0(1) 0(1)
Usunąć 0(N) 0(1) 0(log (N)) 0(log(N))

Sterta binarna

Binarne drzewo sterty organizuje wszystkie węzły nadrzędne i podrzędne drzewa w określonej kolejności. W binarnym drzewie sterty węzeł nadrzędny może mieć maksymalnie 2 węzły podrzędne. Wartość węzła nadrzędnego może wynosić:

  • równa lub mniejsza niż wartość węzła podrzędnego.
  • równa lub większa niż wartość węzła podrzędnego.

Powyższy proces dzieli stertę binarną na dwa typy: max sterta i min-sterta.

Maksymalna sterta

Maksymalna sterta to sterta binarna, w której węzeł nadrzędny ma wartość równą lub większą niż wartość węzła podrzędnego. Węzeł główny drzewa ma najwyższą wartość.

Wstawianie elementu do drzewa binarnego Max Heap

Możesz wykonać następujące kroki, aby wstawić element/numer do kolejki priorytetowej w strukturze danych .

  1. Algorytm skanuje drzewo od góry do dołu i od lewej do prawej, aby znaleźć puste miejsce. Następnie wstawia element w ostatnim węźle drzewa.
  2. Po wstawieniu elementu kolejność drzewa binarnego zostaje zakłócona. Musisz zamienić dane między sobą, aby posortować kolejność drzewa binarnego maksymalnej sterty. Musisz tasować dane, aż drzewo spełnia właściwość max-heap.

Algorytm wstawiania elementu do drzewa binarnego Max Heap

Jeśli drzewo jest puste i nie zawiera żadnego węzła,

utwórz nowy węzeł nadrzędny newElement.

w przeciwnym razie (węzeł nadrzędny jest już dostępny)

wstaw nowyElement na końcu drzewa (tj. ostatni węzeł drzewa od lewej do prawej).

maksymalizuj drzewo

Usuwanie elementu z drzewa binarnego Max Heap

  1. Możesz wykonać następujące kroki, aby usunąć element z kolejki priorytetów w strukturze danych .
  2. Wybierz element, który chcesz usunąć z drzewa binarnego.
  3. Przesuń dane na końcu drzewa, zamieniając je z danymi ostatniego węzła.
  4. Usuń ostatni element drzewa binarnego.
  5. Po usunięciu elementu kolejność drzewa binarnego zostaje zakłócona. Musisz posortować kolejność, aby spełniała właściwość max-heap. Musisz tasować dane, dopóki drzewo nie spełni właściwości max-heap.

Algorytm usuwania elementu w drzewie binarnym Max Heap

Jeśli elementUpForDeletion jest ostatnim węzłem,

usuń elementUpForDeletion

w przeciwnym razie zamień elementUpForDeletion na lastNode

usuń elementUpForDeletion

maksymalizuj drzewo

Znajdź maksymalny lub minimalny element w drzewie binarnym Max Heap

W drzewie binarnym maksymalnej sterty operacja znajdowania zwraca węzeł nadrzędny (najwyższy element) drzewa.

Algorytm znajdowania wartości maksymalnej lub minimalnej w drzewie binarnym maksymalnej sterty

return ParentNode

Programowa realizacja kolejki priorytetowej przy użyciu drzewa binarnego Max Heap

#włącz <stdio.h>

int drzewo_binarne = 10;

int max_sterta = 0;

const int test = 100000;

void swap( int *x, int *y ) {

int;

a = *x;

*x= *y;

*y = a;

}

//Kod do znalezienia rodzica w drzewie max sterty

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

if ((root > 1) && (root < drzewo_binarne)) {

zwróć root/2;

}

powrót -1;

}

void max_heapify(int node[], int root) {

int leftNodeRoot = znajdźLeftChild(węzeł, root);

int prawyNodeRoot = znajdźPraweDziecko(węzeł, korzeń);

// znalezienie najwyższego wśród korzenia, lewego dziecka i prawego dziecka

int najwyższy = korzeń;

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

if (węzeł[leftNodeRoot] > węzeł[najwyższy]) {

najwyższy = lewyNodeRoot;

}

}

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

if (węzeł[prawyWęzełRoot] > węzeł[najwyższy]) {

najwyższy = prawyNodeRoot;

}

}

if (najwyższy != root) {

swap(&węzeł[główny], &węzeł[najwyższy]);

max_heapify(węzeł, najwyższy);

}

}

void create_max_heap(int node[]) {

int d;

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

max_heapify(węzeł, d);

}

}

int maksimum(int węzeł[]) {

węzeł zwrotny [1];

}

int find_max(int ​​węzeł[]) {

int maxNode = node[1];

węzeł[1] = węzeł[maksymalna_sterta];

max_sterta–;

max_heapify(węzeł, 1);

zwróć maxNode;

}

void migrate_key(int node[], int node, int key) {

A[korzeń] = klucz;

max_heapify(węzeł, root);

}

void Increase_key(int node[], int root, int key) {

węzeł[root] = klucz;

while((root>1) && (węzeł[znajdźWęzełNadrzędny(węzeł, root)] < węzeł[root])) {

swap(&węzeł[root], &węzeł[findParentNode(węzeł, root)]);

root = findParentNode(węzeł, root);

}

}

void wstaw(int węzeł[], int klucz) {

max_sterta++;

węzeł[maks_sterta] = -1*test;

Increase_key(węzeł, max_heap, klucz);

}

void display_heap(int node[]) {

int d;

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

printf(„%d\n”, węzeł[d]);

}

printf(„\n”);

}

int main() {

int węzeł[drzewo_binarne];

wstaw(węzeł, 10);

wstaw(węzeł, 4);

wstaw(węzeł, 20);

wstaw(węzeł, 50);

wstaw(węzeł, 1);

wstaw(węzeł, 15);

sterta_wyświetlania(węzeł);

printf(„%d\n\n”, maksimum(węzeł));

sterta_wyświetlania(węzeł);

printf(„%d\n”, extract_max(węzeł));

printf(„%d\n”, extract_max(węzeł));

zwróć 0;

}

Min stos

Kopiec min to sterta binarna, w której węzeł nadrzędny ma wartość równą lub mniejszą niż wartość węzła podrzędnego. Najniższą wartość ma węzeł główny drzewa.

Kopiec minimalny można zaimplementować w taki sam sposób, jak stos maksymalny, z wyjątkiem odwrócenia kolejności.

Wniosek

Przykłady podane w artykule mają jedynie charakter wyjaśniający. Możesz modyfikować powyższe oświadczenia zgodnie z własnymi wymaganiami. Na tym blogu poznaliśmy pojęcie kolejki priorytetowej w strukturze danych . Możesz wypróbować ten przykład, aby wzmocnić swoją wiedzę o strukturze danych.

Jeśli jesteś zainteresowany nauką o danych, sprawdź program IIIT-B i upGrad Executive PG w dziedzinie Data Science, który jest stworzony dla pracujących profesjonalistów i oferuje ponad 10 studiów przypadków i projektów, praktyczne warsztaty praktyczne, mentoring z ekspertami z branży, 1 -on-1 z mentorami branżowymi, ponad 400 godzin nauki i pomocy w pracy z najlepszymi firmami.

Ucz się online kursów nauki o danych z najlepszych światowych uniwersytetów. Zdobywaj programy Executive PG, Advanced Certificate Programs lub Masters Programs, aby przyspieszyć swoją karierę.

Jakie są zastosowania kolejki priorytetowej?

Kolejka priorytetowa to specjalna kolejka, w której elementy są wstawiane na podstawie ich priorytetu. Ta funkcja staje się przydatna w implementacji różnych innych struktur danych. Oto niektóre z najpopularniejszych aplikacji kolejki priorytetowej:
 1. Algorytm najkrótszej ścieżki Dijkstry: Kolejka priorytetowa może być używana w algorytmie najkrótszej ścieżki Dijkstry, gdy wykres jest przechowywany w postaci listy sąsiedztwa.
 2. Algorytm Prima : Algorytm Prima wykorzystuje kolejkę priorytetów do wartości lub kluczy węzłów i wyciąga minimum tych wartości na każdym kroku.
 Kompresja danych : kody Huffmana używają kolejki priorytetowej do kompresji danych.
 Systemy operacyjne: Kolejka priorytetów jest bardzo przydatna w przypadku systemów operacyjnych w różnych procesach, takich jak równoważenie obciążenia i obsługa przerwań.

Jakie podejście stosuje się przy implementacji kolejki priorytetowej za pomocą tablicy?

Podejście zastosowane w implementacji kolejki priorytetowej przy użyciu tablicy jest proste. Tworzona jest struktura do przechowywania wartości i priorytetu elementu, a następnie tworzona jest tablica tej struktury do przechowywania elementów. W realizacji tej zaangażowane są następujące operacje:
 1. enqueue()-Ta funkcja wstawia elementy na końcu kolejki.
 2. peek() — ta funkcja przemierzy tablicę, aby zwrócić element o najwyższym priorytecie. Jeśli znajdzie dwa elementy o tym samym priorytecie, zwraca element o najwyższej wartości spośród nich.
 3. dequeue() - Ta funkcja przesunie wszystkie elementy o 1 pozycję na lewo od elementu zwracanego przez funkcję peek() i zmniejszy rozmiar.

Jaka jest różnica między maksymalną stertą a min stertą?

Poniżej przedstawiono różnicę między maksymalną stertą a min-stertą.
 Sterta min — w stercie min klucz węzła głównego musi być mniejszy lub równy kluczom węzła podrzędnego. Używa priorytetu rosnącego. Węzeł z najmniejszym kluczem jest priorytetem. Najmniejszy element jest wyskakiwany przed jakimkolwiek innym elementem.
 Max sterta — w maksymalnej stercie klucz węzła głównego musi być większy lub równy kluczowi jego węzłów podrzędnych. Używa malejącego priorytetu. Węzeł z największym kluczem jest priorytetem. Największy element jest wyskakiwany przed jakimkolwiek innym elementem.