პრიორიტეტული რიგი  


Რთული ტური Easy
ხშირად ეკითხებიან Amazon ავალარა CodeNation Goldman Sachs Google microsoft
Queue თეორია

პრიორიტეტული მდგომ არის მონაცემთა სტრუქტურის ტიპი, რომელიც მსგავსია რეგულარული რიგისა, მაგრამ პრიორიტეტი ასოცირდება მის თითოეულ ელემენტთან. უფრო მაღალი პრიორიტეტი ადრე ემსახურება ელემენტს. ზოგიერთ შემთხვევაში, ორი ელემენტია იგივე პრიორიტეტით, შემდეგ, პირველ რიგში, მოყვანილი ელემენტი მოემსახურება.

მაგალითი  

დავუშვათ, არსებობს ორი სამუშაო ადგილი, კერძოდ, A და B, სადაც სამუშაო A– ს უფრო მაღალი პრიორიტეტია ვიდრე სამუშაო B. მოდით სამუშაოს დანიშვნა იყოს შემდეგი თანმიმდევრობით

  1. A
  2. B
  3. A

შემდეგი თანმიმდევრობით ჩამოყალიბდება პრიორიტეტული რიგი:

პრიორიტეტული რიგი პრიორიტეტული რიგიPin

ასე რომ, აქ ხედავთ, რომ უფრო მაღალი პრიორიტეტის მქონე სამუშაოები მინიჭებულია უფრო პრიორიტეტული სამუშაოების დაწყებამდე.

პრიორიტეტული რიგის სახეები  

  1. აღმავალი შეკვეთის პრიორიტეტული რიგი

    ამ ტიპის პრიორიტეტულ_წყრილში უფრო დაბალი პრიორიტეტული ნომერი ენიჭება უფრო პრიორიტეტულ სამუშაოებს.
    მაგალითად: თუ ორ სამუშაო ადგილს, კერძოდ, A და B ენიჭება ნომრები 1 და 2, სადაც სამუშაო უფრო მაღალი პრიორიტეტია, A– ს მიენიჭება 1, ხოლო სამუშაო B– ს 2.

  2. კლების რიგის პრიორიტეტული რიგი

    ამ ტიპის პრიორიტეტულ_კონტაქტში უფრო მაღალი პრიორიტეტის მქონე სამუშაოებს ენიჭებათ უფრო პრიორიტეტული ნომერი.
    მაგალითად: თუ ორ სამუშაო ადგილს, კერძოდ, A და B ენიჭება ნომრები 1 და 2, სადაც სამუშაო უფრო მაღალი პრიორიტეტია, A– ს მიენიჭება 2, ხოლო სამუშაო B– ს 1.

პრიორიტეტული რიგის მიერ შესრულებული ოპერაცია  

ძირითადი ოპერაციები, რომლებიც შესრულებულია პრიორიტეტულ_კონტაქტით, შემდეგია:

  1. ჩასმა: ჩადეთ ნივთი რიგში მისი პრიორიტეტის შესაბამისად.
  2. წაშლა: ხსნის ნივთს რიგიდან.
  3. getHighestPriority: გაძლევთ ყველაზე მაღალ პრიორიტეტულ ელემენტს.

Priority_queue კიდევ რამდენიმე ოპერაციას უჭერს მხარს:

  1. დაჰყურებს: მიიღეთ ელემენტი რიგის წინ.
  2. სავსეა: ამოწმებს რიგის შევსებას.
  3. ცარიელია: ამოწმებს თუ არა რიგი ცარიელი.

პროგრამები  

  1. დაგეგმვისას, როგორიცაა პროცესორის დაგეგმვა, დისკის დანიშვნა და ა.შ.
  2. დიაგრამის ალგორითმები (Dijkstra- ს უმოკლესი გზის ალგორითმი, Prim- ის მინიმალური გაშლის ხე და ა.შ.)

განხორციელება  

პრიორიტეტული რიგის განხორციელება შესაძლებელია მონაცემთა სხვადასხვა სტრუქტურის გამოყენებით, როგორიცაა მასივი, დაკავშირებული სია და ა.შ. მონაცემთა ზოგიერთი სტრუქტურა მოცემულია ქვემოთ მათი დროის სირთულეებით:

  1. მასივები (O (n * ჟურნალი (n)))
  2. დაკავშირებული სია (O (n)
  3. გროვა (O (ჟურნალი (n)))

მონაცემთა სტრუქტურიდან ბევრი მონაცემთა სტრუქტურა უზრუნველყოფს დროის საუკეთესო სირთულეს პრიორიტეტული_წყობის განხორციელებისას.

ლიტერატურა

იხილეთ ასევე
სტეკების გამოყენებით რიგში დგომა