Kolejka priorytetowa

Poziom trudności Łatwo
Często zadawane pytania Amazonka Avalara KodNation Goldman Sachs Google Microsoft
kolejka Teoriaodwiedzajacy 65

Pytania do rozmowy kwalifikacyjnej na temat projektowania systemu może być tak nieograniczona, że ​​trudno jest określić właściwy sposób przygotowania. Teraz jestem w stanie złamać rundy projektowe Amazon, Microsoft i Adobe po zakupie ta książka. Codziennie poprawiaj jeden pytanie projektowe i obiecuję, że możesz złamać cały projekt.

Priorytet kolejka to rodzaj struktury danych, która jest podobna do zwykłej kolejki, ale ma priorytet powiązany z każdym jej elementem. Im wyższy priorytet, tym wcześniej element będzie obsługiwany. W niektórych przypadkach istnieją dwa elementy o tym samym priorytecie, wtedy element umieszczony w kolejce jako pierwszy zostanie obsłużony jako pierwszy.

Przykład

Załóżmy, że istnieją 2 zadania, a mianowicie A i B, w których zadanie A ma wyższy priorytet niż zadanie B. Niech planowanie zadań będzie w następującej kolejności:

  1. A
  2. B
  3. A

W następującej kolejności utworzona zostanie kolejka priorytetowa:

Kolejka priorytetowa Kolejka priorytetowaszpilka

Tutaj widać, że zadania o wyższym priorytecie są przypisywane przed zadaniami o niższym priorytecie.

Rodzaje kolejek priorytetowych

  1. Kolejka priorytetowa w kolejności rosnącej

    W tym typie priority_queue zadania o wyższym priorytecie mają niższy priorytet.
    Na przykład: Jeśli dwóm zadaniom, a mianowicie A i B, zostaną przypisane numery 1 i 2, gdzie zadanie A ma wyższy priorytet, wówczas A otrzyma 1, a zadanie B - 2.

  2. Kolejka priorytetowa kolejności malejącej

    W tym typie Priority_queue zadaniom o wyższym priorytecie przypisywany jest wyższy numer priorytetu.
    Na przykład: Jeśli dwóm zadaniom, a mianowicie A i B, zostaną przypisane numery 1 i 2, gdzie zadanie A ma wyższy priorytet, wówczas A otrzyma 2, a zadanie B - 1.

Operacja wykonywana przez kolejkę priorytetową

Podstawowe operacje wykonywane przez Priority_queue są następujące:

  1. Wprowadzenie: Wstaw element do kolejki zgodnie z jego priorytetem.
  2. Kasować: Usuwa element z kolejki.
  3. uzyskajNajwyższyPriorytet: Daje element o najwyższym priorytecie.

Priority_queue obsługuje jeszcze kilka operacji:

  1. Zerkać: Pobierz element na początku kolejki.
  2. jest pełne: sprawdza, czy kolejka jest pełna.
  3. jest pusty: sprawdza, czy kolejka jest pusta.

Konsultacje

  1. W planowaniu, takim jak planowanie procesora, planowanie dysków itp.
  2. Algorytmy wykresów (algorytm najkrótszej ścieżki Dijkstry, minimalne drzewo rozpinające Prim itp.)

Realizacja

Kolejkę priorytetową można zaimplementować przy użyciu różnych struktur danych, takich jak tablica, lista połączona itp. Niektóre struktury danych są podane poniżej wraz z ich złożonością czasową:

  1. Tablice (O (n * log (n)))
  2. Lista połączona (O (n)
  3. Sterta (O (log (n)))

Ze wszystkich struktur danych struktura danych sterty zapewnia najlepszą złożoność czasową podczas implementacji Priority_queue.

Referencje

Wywiady dotyczące projektowania systemu pękania
Translate »