Menu

Struktura danych kolejki priorytetowej w C ++ z ilustracjami

  • Główny
  • Inny
  • Struktura danych kolejki priorytetowej w C ++ z ilustracjami

priority queue data structure c with illustration

Wprowadzenie do kolejki priorytetowej w C ++ z ilustracją.

Priority Queue to rozszerzenie kolejki, które omówiliśmy w naszym ostatnim samouczku.

Pod pewnymi względami jest podobny do kolejki, ale różni się od zwykłej kolejki w następujących punktach:

  • Każda pozycja w kolejce priorytetów ma przypisany priorytet.
  • Element o najwyższym priorytecie jest pierwszym elementem usuwanym z kolejki.
  • Jeśli więcej niż jedna pozycja ma ten sam priorytet, brana jest pod uwagę ich kolejność w kolejce.

=> Kliknij tutaj, aby zapoznać się z serią szkoleń Absolute C ++.

Kolejka priorytetowa w C ++

Możemy wizualizować kolejkę priorytetową jako zmodyfikowaną wersję kolejki, z tym wyjątkiem, że gdy pozycja ma zostać usunięta z kolejki, najpierw pobierana jest pozycja o najwyższym priorytecie. Dlatego wolimy używać kolejek priorytetowych zamiast kolejek, gdy musimy przetwarzać elementy na podstawie priorytetu.

Czego się nauczysz:

Podstawowe operacje

Omówmy kilka podstawowych operacji obsługiwanych przez kolejkę priorytetową.

  • Wstaw (pozycja, priorytet): Wstawia element do kolejki priorytetowej z określonym priorytetem.
  • getHighestPriority (): Zwraca element o najwyższym priorytecie.
  • deleteHighestPriority (): Usuwa element o najwyższym priorytecie.

Oprócz powyższych operacji, możemy również użyć normalnych operacji kolejkowych, takich jak isEmpty (), isFull () i peek ().

Ilustracja

Zobaczmy ilustrację kolejki priorytetowej. Dla uproszczenia będziemy używać znaków ASCII jako pozycji w kolejce priorytetowej. Im wyższa wartość ASCII, tym wyższy priorytet.

Stan początkowy - kolejka priorytetowa (PQ) - {} => pusty

ilustracja kolejki priorytetowej

Na powyższej ilustracji widzimy, że operacja wstawiania jest podobna do zwykłej kolejki. Ale kiedy wywołujemy metodę „deleteHighestPriority” dla kolejki priorytetowej, element o najwyższym priorytecie jest usuwany jako pierwszy.

Stąd za pierwszym razem, gdy wywołujemy tę funkcję, element O jest usuwany, podczas gdy za drugim razem element M jest usuwany, ponieważ ma wyższy priorytet niż G i A.

Implementacja kolejek priorytetowych w C ++

Kolejki priorytetowe można realizować za pomocą:

# 1) Tablice / listy połączone

Możemy zaimplementować kolejki priorytetowe za pomocą tablic i jest to najprostsza implementacja dla kolejek priorytetowych.

Aby reprezentować pozycje w kolejce priorytetowej, możemy po prostu zadeklarować strukturę jak poniżej:

struct pq_item{ int item; int priority; };

Dla każdej pozycji zadeklarowaliśmy również priorytet.

Aby wstawić nowy element do kolejki priorytetów, wystarczy wstawić go na końcu tablicy.

Aby pobrać element z kolejki za pomocą metody getHighestPriority (), musimy przejść przez tablicę od początku i zwrócić element o najwyższym priorytecie.

Podobnie, aby usunąć element z kolejki za pomocą operacji deleteHighestPriority, musimy przejść przez całą tablicę i usunąć element o najwyższym priorytecie. Następnie przenieś wszystkie pozostałe elementy po usuniętym elemencie o jedną pozycję do tyłu.

Możemy również zaimplementować kolejkę priorytetową za pomocą połączonej listy. Wszystkie operacje możemy wykonywać w podobny sposób jak tablice. Jedyną różnicą jest to, że nie musimy przenosić elementów po wywołaniu metody deleteHighestPriority.

# 2) Stosy

Używanie stert do implementacji kolejki priorytetowej jest najbardziej wydajnym sposobem i zapewnia znacznie lepszą wydajność w porównaniu z połączonymi listami i tablicami. W przeciwieństwie do połączonej listy i tablicy, implementacja sterty zajmuje O (logowanie) czasu operacji wstawiania i usuwania kolejki priorytetowej. Uzyskaj operację, getHighestPriority zajmuje O (1) czasu.

# 3) Wbudowana kolejka priorytetów w standardowej bibliotece szablonów (STL) w C ++

W C ++ mamy kolejkę priorytetową jako kontenerową klasę adaptacyjną, zaprojektowaną w taki sposób, że najwyższy element jest pierwszym elementem kolejki, a wszystkie elementy są w kolejności malejącej.

W ten sposób każda pozycja w kolejce priorytetowej ma ustalony priorytet.

Mamy klasę w STL, która zawiera implementację kolejki priorytetowej.

Różne operacje obsługiwane przez kolejkę priorytetową są następujące:

  1. Priority_queue :: size (): Zwraca rozmiar kolejki.
  2. Priority_queue :: empty (): Sprawdza, czy kolejka jest pusta i zwraca jej stan.
  3. Priority_queue :: top (): Zwraca odniesienie do najwyższego elementu kolejki priorytetowej.
  4. Priority_queue :: push (): Dodaje element na końcu kolejki priorytetowej.
  5. Priority_queue :: pop (): Usuwa pierwszy element z kolejki priorytetowej.
  6. Priority_queue :: swap (): Służy do zamiany zawartości jednej kolejki priorytetowej na inną tego samego typu i rozmiaru.
  7. typ wartości kolejki priorytetowej: Typ wartości określa typ elementu przechowywanego w kolejce priorytetowej. Działa to również jako synonim parametru szablonu.
  8. Priority_queue :: embrace (): Służy do wstawiania nowego elementu w kontenerze kolejki priorytetowej na górze kolejki.

W kolejnym programie zobaczymy funkcjonalność kolejki priorytetowej w STL w C ++.

#include #include using namespace std; void displaypq(priority_queue pq) { priority_queue pqueue = pq; while (!pqueue.empty()) { cout << ' ' << pqueue.top(); pqueue.pop(); } cout << ' '; } int main () { priority_queue pq; pq.push(1); pq.push(3); pq.push(5); pq.push(7); pq.push(9); cout << 'Size of the queue(pq.size()): ' << pq.size(); cout << ' Top element of the queue(pq.top()): ' << pq.top(); cout << ' The priority queue pq is : '; displaypq(pq); cout << ' Priority queue, after pq.pop() operation : '; pq.pop(); displaypq(pq); return 0; }

Wynik:

jak korzystać z pliku apk

Rozmiar kolejki (pq.size ()): 5
Górny element kolejki (pq.top ()): 9
Kolejka priorytetowa pq to: 9 7 5 3 1
Kolejka priorytetowa po operacji pq.pop (): 7 5 3 1

Implementacja Java dla kolejki priorytetowej

Kolejka priorytetowa w java to specjalna kolejka, w której wszystkie elementy w kolejce są uporządkowane według kolejności naturalnej lub niestandardowej za pomocą komparatora dostarczanego z kolejką.

Kolejka priorytetowa w Javie wygląda jak poniżej:

Implementacja Java dla kolejki priorytetowej

W kolejce priorytetowej Java elementy są ułożone w taki sposób, że najmniejszy element znajduje się z przodu kolejki, a największy z tyłu kolejki. Kiedy więc usuwamy element z kolejki priorytetowej, zawsze usuwany jest najmniejszy element.

Klasa implementująca kolejkę priorytetów w Javie to „PriorityQueue” i jest częścią struktury kolekcji Java. Implementuje interfejs „Queue” języka Java.

Poniżej przedstawiono hierarchię klas dla klasy PriorityQueue języka Java.

hierarchia klas dla klasy PriorityQueue języka Java

Poniżej podano przykład funkcjonalności kolejki priorytetowej z liczbami całkowitymi jako elementami w języku Java.

import java.util.*; class Main { public static void main(String args[]) { // Create empty priority queue PriorityQueue priority_Queue = new PriorityQueue(); // Adding items to the priority_Queue using add() priority_Queue.add(1); priority_Queue.add(3); priority_Queue.add(5); priority_Queue.add(7); // display the most priority element System.out.println('peek()::Head value:' + priority_Queue.peek()); // Print all elements in Priotity queue System.out.println('The priority queue:'); Iterator itr = priority_Queue.iterator(); while (itr.hasNext()) System.out.print(itr.next() + ' '); // poll() function to remove the queue elements priority_Queue.poll(); System.out.println(' After poll() function, priority queue:'); Iterator itr2 = priority_Queue.iterator(); while (itr2.hasNext()) System.out.print(itr2.next() + ' '); // remove() function with priority queue priority_Queue.remove(5); System.out.println(' After Remove(5) function, priority queue:'); Iterator itr3 = priority_Queue.iterator(); while (itr3.hasNext()) System.out.print(itr3.next() + ' '); // Check if an element is present using contains() boolean b = priority_Queue.contains(3); System.out.println ( ' Priority queue contains 3?: ' + b); // use toArray() function to get objects from the queue and display the array elements Object[] arr = priority_Queue.toArray(); System.out.println ( 'Array elements: '); for (int i = 0; i

Wynik:

peek () :: Wartość nagłówka: 1
Kolejka priorytetowa:
1 3 5 7
Po funkcji poll () kolejka priorytetowa:
3 7 5
Po funkcji Remove (5) kolejka priorytetowa:
3 7
Kolejka priorytetowa zawiera 3 ?: prawda
Elementy tablicy:
Wartość: 3
Wartość: 7

W powyższym programie wykorzystujemy klasę PriorityQueue języka Java do stworzenia obiektu PriorityQueue, który zawiera obiekt Integer. Dodajemy elementy do kolejki za pomocą funkcji „add”. Następnie wywoływana jest funkcja poll (), która usuwa element z początku kolejki, który jest najmniejszym elementem.

Ponownie wywołujemy funkcję „remove ()”, która usuwa element określony jako parametr z kolejki. Używamy również funkcji „Contains ()”, aby sprawdzić, czy dany element jest obecny w kolejce. Na koniec konwertujemy kolejkę na obiekt tablicowy za pomocą funkcji „toArray ()”.

Podanie

  • Równoważenie obciążenia systemu operacyjnego i programy obsługi przerwań: Funkcje systemu operacyjnego, takie jak równoważenie obciążenia i obsługa przerwań, są realizowane za pomocą kolejek priorytetowych. Działanie równoważenia obciążenia planuje zasoby o najwyższym priorytecie w celu efektywnego równoważenia obciążenia. Obsługa przerwań odbywa się poprzez obsługę przerwań o najwyższym priorytecie. Funkcjonalność tę można skutecznie wdrożyć przy użyciu kolejek priorytetowych.
  • Wytyczanie: Routing to funkcja służąca do trasowania zasobów sieciowych, tak aby uzyskać maksymalną przepustowość przy minimalnym czasie realizacji. Można to również zrealizować za pomocą kolejki priorytetowej.
  • Pogotowie szpitalne: Na szpitalnej izbie przyjęć pacjenci są obsługiwani w zależności od ciężkości stanu pacjenta. Można to zasymulować za pomocą kolejek priorytetowych.
  • Algorytm najkrótszej ścieżki Dijkstry: Tutaj wykres jest przechowywany jako lista przylegania i możemy użyć kolejki priorytetowej, aby efektywnie wyodrębnić minimalną ważoną krawędź z listy przylegania, aby zaimplementować algorytm najkrótszej ścieżki Dijkstry.
  • Kolejka priorytetowa może być również używana do przechowywania kluczy węzłów i wyodrębniania minimalnego węzła kluczy podczas implementowania drzewa opinającego.

Wniosek

Kolejki priorytetowe to nic innego jak przedłużenie kolejki. Ale w przeciwieństwie do kolejek, które dodają / usuwają pozycje przy użyciu podejścia FIFO, w kolejce priorytetowej pozycje są usuwane z kolejki zgodnie z priorytetem. W ten sposób każda pozycja w kolejce ma przypisany priorytet, a pozycja o najwyższym priorytecie jest usuwana jako pierwsza z kolejki.

Kolejka priorytetowa ma trzy główne operacje, tj. Insert (), getHighestPriority () i deleteHighestPriority (). Kolejka priorytetowa może zostać zaimplementowana przy użyciu tablic lub połączonych list, ale praca nie jest zbyt wydajna. Kolejkę priorytetową można również zaimplementować za pomocą stert, a wydajność jest znacznie szybsza.

W C ++ mamy również klasę kontenera, która implementuje funkcjonalność kolejki priorytetowej. W Javie istnieje wbudowana klasa Priority_queue, która zapewnia funkcjonalność kolejki priorytetowej.

Kolejka priorytetowa jest używana głównie w aplikacjach, które wymagają przetwarzania elementów zgodnie z priorytetem. Na przykład, jest używany w obsłudze przerwań.

W naszym nadchodzącym samouczku omówimy wszystko o kolejce cyklicznej, która jest kolejnym rozszerzeniem kolejki.

=> Odwiedź tutaj, aby zapoznać się z pełnym kursem C ++ od ekspertów.

rekomendowane lektury

^