Prioritetskø

Sværhedsniveau Easy
Ofte stillet ind Amazon Avalara CodeNation Goldman Sachs google microsoft
TeoriViews 66

Systemdesign interviewspørgsmål kan være så åben, at det er for svært at kende den rigtige måde at forberede sig på. Nu er jeg i stand til at knække designrunderne fra Amazon, Microsoft og Adobe efter køb denne bog. Daglig revision af en design spørgsmål og jeg lover, at du kan knække designrunden.

En prioritet er en type datastruktur, der ligner en almindelig kø, men som har en prioritet tilknyttet hvert af dets element. Højere prioritet tidligere vil elementet blive serveret. I nogle tilfælde er der to elementer med samme prioritet, så det element, der er indkapslet først, serveres først.

Eksempel

Antag, at der er 2 job, nemlig A og B, hvor job A har højere prioritet end job B. Lad planlægningen af ​​job være i følgende rækkefølge:

  1. A
  2. B
  3. A

I den følgende rækkefølge dannes prioritetskø:

Prioritetskø PrioritetskøPin

Så her ser du, at job med højere prioritet tildeles før job med lavere prioritet.

Typer af prioritetskø

  1. Stigende kø for prioritetsordre

    I denne type prioritets_tilstand tildeles et job med højere prioritet et lavere prioritetsnummer.
    For eksempel: Hvis to job, nemlig A og B, tildeles nummer 1 og 2, hvor job A har højere prioritet, tildeles A 1, og job B tildeles 2.

  2. Faldende rækkefølge prioritets kø

    I denne type prioritetskøbe tildeles job med højere prioritet et højere prioritetsnummer.
    For eksempel: Hvis to job, nemlig A og B, tildeles nummer 1 og 2, hvor job A har højere prioritet, tildeles A 2, og job B tildeles 1.

Betjening udført af Priority Queue

De grundlæggende operationer, der udføres af en prioritets-kø, er som følger:

  1. Indskud: Indsæt et element i køen i henhold til dets prioritet.
  2. Slette: Fjerner et element fra køen.
  3. getHighestPrioritet: Giver dig elementet med højeste prioritet.

Priority_queue understøtter et par flere operationer:

  1. Kig: Få elementet foran køen.
  2. er fuld: kontrollerer, om køen er fuld.
  3. er tom: kontrollerer, om køen er tom.

Applikationer

  1. I planlægning som CPU-planlægning, Diskplanlægning osv.
  2. Grafalgoritmer (Dijkstras korteste algoritme, Prims mindst spændende træ osv.)

Implementering

Prioritetskø kan implementeres ved hjælp af forskellige datastrukturer som en matrix, sammenkædet liste osv. Nogle af datastrukturer er angivet nedenfor med deres tidskompleksitet:

  1. Arrays (O (n * log (n)))
  2. Tilknyttet liste (O (n)
  3. Bunke (O (log (n)))

Ud af al datastruktur giver bunke datastruktur den bedste tidskompleksitet, mens du implementerer en prioritets_kø.

Referencer

Crack System Design Interviews
Translate »